Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Games of ordinal Length

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

Date
Le lundi 06 avril 2009 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
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.


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

mar. 19 février

Les séminaires précédents