1 Search Results for "Fridman, Wladimir"

Document
DOI: 10.4230/LIPIcs.CSL.2011.264
Degrees of Lookahead in Context-free Infinite Games

Authors: Wladimir Fridman, Christof Löding, and Martin Zimmermann

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

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.
Cite as

Wladimir Fridman, Christof Löding, and Martin Zimmermann. Degrees of Lookahead in Context-free Infinite Games. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 264-276, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{fridman_et_al:LIPIcs.CSL.2011.264,
  author =	{Fridman, Wladimir and L\"{o}ding, Christof and Zimmermann, Martin},
  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 =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.264},
  URN =		{urn:nbn:de:0030-drops-32365},
  doi =		{10.4230/LIPIcs.CSL.2011.264},
  annote =	{Keywords: infinite games, delay, context-free languages}
}
  • Refine by Author
  • 1 Fridman, Wladimir
  • 1 Löding, Christof
  • 1 Zimmermann, Martin

  • Refine by Classification

  • Refine by Keyword
  • 1 context-free languages
  • 1 delay
  • 1 infinite games

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2011

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact