LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.

Past Seminars

Games of ordinal Length

Monday, April 06 2009 at 11:00AM
Salle de Conférence (Pavillon des Jardins)
Florian Horn (CWI, Amsterdam)

We present an extension of the classical model of infinite two-player games, allowing plays with arbitrary ordinal length. In addition to the usual ''successor transitions'', our arenas feature ''limit transitions'' which describe what happens after partial plays whose length is a limit ordinal. The play only stops when it reaches a final state, which can be winning for either of the players.
We describe two solutions for such games. The first one uses a reduction to infinite Muller games, and shows that the problem of the winner is PSPACE-complete. The second one uses a special case of ordinal games with ''priority'' transitions, where the players have positional strategies. A LAR-like construction allows us to derive the existence of finite-memory strategies in the general case.

About LSV