AIB 2010-20: Degrees of Lookahead in Context-free Infinite Games

The following technical report is available from http://aib.informatik.rwth-aachen.de: Degrees of Lookahead in Context-free Infinite Games Wladimir Fridman, Christof Löding, Martin Zimmermann AIB 2010-20 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.