2026-07-21T20:32:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3236 2024-03-06T10:33:59Z ddc:004 open_access

Degrees of Lookahead in Context-free Infinite Games Fridman, Wladimir Löding, Christof Zimmermann, Martin infinite games delay context-free languages 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wladimir Fridman and Christof Löding and Martin Zimmermann 2011 Is Part Of LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2011.264 urn:nbn:de:0030-drops-32365 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.264 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode