29 Dez
2010
29 Dez
'10
22:24
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.