Degrees of Lookahead in Context-free Infinite Games
Wladimir Fridman and Christof Löding, and Martin Zimmermann
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 opponents moves. We show that the problem of determining the winner of such a game is undecidable for context-free winning conditions. Furthermore, we show that the necessary lookahead to win a context-free delay game cannot be bounded by an elementary function.