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
Playing games when states have rich structure
- Date
- Tuesday, April 12 2011 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Lukasz Kaiser (LIAFA, CNRS, Université Paris Diderot - Paris VII)
Both in the classical theory of extensive-form games and in the more recent theory of games on graphs it is normally assumed that a state of the game has no structure beyond the outgoing moves. In other words, the internal structure of the states is abstracted away. This is very useful in some cases, but can be a hindrance in others, for example when studying games on pushdown graphs or on timed automata. To better understand how internal structure of the states can influence behaviour of the players, we introduce a general model of games with structured states. In our model, actions of the players are given by structure rewriting rules and winning conditions by logic formulas. In case of games with perfect information, we show that the structure of the states can be exploited to create simple strategies, sometimes even when the number of states in the game is infinite. This is similar to games on pushdown graphs and indeed, we prove a close relationship between pushdown games and our model when rewriting rules are of a certain simple form.