joint work with Wladimir Fridman and Christof Löding

Speaker(s)

Martin Zimmermann

Affiliation

Uniwersytet Warszawski

Date

Oct. 24, 2012, 2:15 p.m.

Room

room 5870

Title in Polish

Degrees of Lookahead in Context-free Infinite Games

Seminar

Seminar Automata Theory

---

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.

---