Degrees of Lookahead in Context-free Infinite Games

Prelegent(ci)

Martin Zimmermann

Afiliacja

Uniwersytet Warszawski

Termin

24 października 2012 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Wladimir Fridman and Christof Löding

Seminarium

Seminarium „Teoria automatów”

---

We consider delay games, infinite games in which one player may
postpone her moves for some time to obtain a lookahead on her
opponent's moves. For regular winning conditions, Hosch and Landweber
and later Holtmann, Kaiser, and Thomas showed that constant delay
suffices and the winner can be determined effectively.

We show that the problem of determining the winner of such a game is
undecidable for deterministic context-free winning conditions.
Furthermore, we show that the necessary lookahead to win a
deterministic context-free delay game cannot be bounded by any
elementary function. Both results hold already for restricted classes
of deterministic context-free winning conditions.

---