Degrees of Lookahead in Context-free Infinite Games
Wladimir Fridman, Christof Löding, Martín Zimmermann · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2011
We continue the investigation of delay games, infinite games in which one player may postpone her moves for some time to obtain a lookahead on her opponent's moves. 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.