Degrees of lookahead in context-free infinite games



Fridman, W, Löding, C and Zimmermann, M ORCID: 0000-0002-8038-2453
(2011) Degrees of lookahead in context-free infinite games. .

[img] 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