by Wladimir Fridman, Christof Löding, Martin Zimmermann
Reference:
Degrees of Lookahead in Context-free Infinite Games (Wladimir Fridman, Christof Löding, Martin Zimmermann), In Computer Science Logic (CSL’11) – 25th International Workshop/20th Annual Conference of the EACSL (Marc Bezem, ed.), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, volume 12, 2011.
Bibtex Entry:
@inproceedings{FLZ11, author = {Fridman, Wladimir and L{"o}ding, Christof and Zimmermann, Martin}, title = {Degrees of {L}ookahead in {C}ontext-free {I}nfinite {G}ames}, booktitle = {Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL}, pages = {264--276}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-32-3}, ISSN = {1868-8969}, year = {2011}, volume = {12}, editor = {Marc Bezem}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3236}, URN = {urn:nbn:de:0030-drops-32365}, doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2011.264}, annote = {Keywords: infinite games, delay, context-free languages} abstract = {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.} }