License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.264
URN: urn:nbn:de:0030-drops-32365
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3236/
Go to the corresponding LIPIcs Volume Portal

Fridman, Wladimir ; Löding, Christof ; Zimmermann, Martin

Degrees of Lookahead in Context-free Infinite Games

pdf-format:
23.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{fridman_et_al:LIPIcs:2011:3236,
  author =	{Wladimir Fridman and Christof L{\"o}ding and Martin Zimmermann},
  title =	{{Degrees of Lookahead in Context-free Infinite Games}},
  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 =		{10.4230/LIPIcs.CSL.2011.264},
  annote =	{Keywords: infinite games, delay, context-free languages}
}

Keywords: infinite games, delay, context-free languages
Collection: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue Date: 2011
Date of publication: 31.08.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI