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.
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.