Document Open Access Logo

What are Strategies in Delay Games? Borel Determinacy for Games with Lookahead

Authors Felix Klein, Martin Zimmermann

PDF
Thumbnail PDF

File

LIPIcs.CSL.2015.519.pdf
  • Filesize: 479 kB
  • 15 pages

Document Identifiers

Author Details

Felix Klein
Martin Zimmermann

Cite AsGet BibTex

Felix Klein and Martin Zimmermann. What are Strategies in Delay Games? Borel Determinacy for Games with Lookahead. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 519-533, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CSL.2015.519

Abstract

We investigate determinacy of delay games with Borel winning conditions, infinite-duration two-player games in which one player may delay her moves to obtain a lookahead on her opponent's moves. First, we prove determinacy of such games with respect to a fixed evolution of the lookahead. However, strategies in such games may depend on information about the evolution. Thus, we introduce different notions of universal strategies for both players, which are evolution-independent, and determine the exact amount of information a universal strategy needs about the history of a play and the evolution of the lookahead to be winning. In particular, we show that delay games with Borel winning conditions are determined with respect to universal strategies. Finally, we consider decidability problems, e.g., "Does a player have a universal winning strategy for delay games with a given winning condition?", for omega-regular and omega-context-free winning conditions.
Keywords
  • Determinacy
  • Infinite Games
  • Delay Games
  • Borel Hierarchy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alonzo Church. Applications of recursive arithmetic to the problem of circuit synthesis. In Summaries of the Summer Institute of Symbolic Logic, volume 1, pages 3-50. Cornell University, 1957. Google Scholar
  2. Rina S. Cohen and Arie Y. Gold. ω-computations on deterministic pushdown machines. J. Comput. Syst. Sci., 16(3):275-300, 1978. Google Scholar
  3. E. Allen Emerson and Charanjit S. Jutla. Tree automata, mu-calculus and determinacy (extended abstract). In FOCS 1991, pages 368-377. IEEE, 1991. Google Scholar
  4. Olivier Finkel. Topological properties of omega context-free languages. Theor. Comput. Sci., 262(1):669-697, 2001. Google Scholar
  5. Olivier Finkel. The determinacy of context-free games. J. Symb. Log., 78(4):1115-1134, 2013. Google Scholar
  6. Wladimir Fridman, Christof Löding, and Martin Zimmermann. Degrees of lookahead in context-free infinite gmes. In Marc Bezem, editor, CSL 2011, volume 12 of LIPIcs, pages 264-276. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011. Google Scholar
  7. Michael Holtmann, Łukasz Kaiser, and Wolfgang Thomas. Degrees of lookahead in regular infinite games. LMCS, 8(3), 2012. Google Scholar
  8. Frederick A. Hosch and Lawrence H. Landweber. Finite delay solutions for sequential conditions. In ICALP 1972, pages 45-60, 1972. Google Scholar
  9. Marcin Jurdziński. Deciding the winner in parity games is in UP ∩ co-UP. Inf. Process. Lett., 68(3):119-124, 1998. Google Scholar
  10. Felix Klein and Martin Zimmermann. How much lookahead is needed to win infinite games? In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, ICALP 2015, volume 9135 of LNCS, pages 452-463. Springer, 2015. Google Scholar
  11. Donald A. Martin. Borel determinacy. Annals of Mathematics, 102:363-371, 1975. Google Scholar
  12. Bastien Maubert and Sophie Pinchinat. A general notion of uniform strategies. IGTR, 16(1), 2014. Google Scholar
  13. Robert McNaughton. Playing infinite games in finite time. In Arto Salomaa, Derick Wood, and Sheng Yu, editors, A Half-Century of Automata Theory, pages 73-91. World Scientific, 2000. Google Scholar
  14. Andrzej Mostowski. Games with forbidden positions. Technical Report 78, University of Gdańsk, 1991. Google Scholar
  15. Wolfgang Thomas and Helmut Lescow. Logical specifications of infinite computations. In J. W. de Bakker, Willem P. de Roever, and Grzegorz Rozenberg, editors, REX 1993, volume 803 of LNCS, pages 583-621. Springer, 1993. Google Scholar
  16. B.A. Trakhtenbrot and I.M. Barzdin. Finite Automata; Behavior and Synthesis. Fundamental Studies in Computer Science, V. 1. North-Holland Publishing Company; New York: American Elsevier, 1973. Google Scholar
  17. Igor Walukiewicz. Pushdown processes: Games and model-checking. Inf. Comput., 164(2):234-263, 2001. Google Scholar
  18. Ernst Zermelo. über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proceedings of the Fifth Congress of Mathematicians, Vol. 2, pages 501-504. Cambridge Press, 1913. Google Scholar
  19. Martin Zimmermann. Delay games with WMSO+U winning conditions. In Lev D. Beklemishev and Daniil V. Musatov, editors, CSR 2015, volume 9139 of LNCS, pages 412-425. Springer, 2015. Google Scholar
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