License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-33897
URL:

The Determinacy of Context-Free Games

pdf-format:


Abstract

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of omega-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W(L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(A), L(B)).

BibTeX - Entry

@InProceedings{finkel:LIPIcs:2012:3389,
  author =	{Olivier Finkel},
  title =	{{The Determinacy of Context-Free Games}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{555--566},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3389},
  URN =		{urn:nbn:de:0030-drops-33897},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2012.555},
  annote =	{Keywords: Automata and formal languages, logic in computer science, Gale-Stewart games, Wadge games, determinacy, context-free games}
}

Keywords: Automata and formal languages, logic in computer science, Gale-Stewart games, Wadge games, determinacy, context-free games
Seminar: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue date: 2012
Date of publication: 2012


DROPS-Home | Fulltext Search | Imprint Published by LZI