Degrees of Lookahead in Context-free Infinite Games

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.