Fridman, W, Löding, C and Zimmermann, M ORCID: 0000-0002-8038-2453
(2011)
Degrees of lookahead in context-free infinite games.
.
Text
flz.pdf - Published version Download (543kB) | Preview |
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. © W. Fridman, C. Löding, and M. Zimmermann.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Depositing User: | Symplectic Admin |
Date Deposited: | 15 Jul 2019 12:51 |
Last Modified: | 19 Jan 2023 00:37 |
DOI: | 10.4230/LIPIcs.CSL.2011.264 |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3049679 |