×

The determinacy of context-free games. (English) Zbl 1349.03038

Summary: 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 \(\mathcal {A}\) and a Büchi automaton \(\mathcal {B}\) such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game \(W(L(\mathcal {A}), L(\mathcal {B}))\); (2) There exists a model of ZFC in which the Wadge game \(W(L(\mathcal {A}), L(\mathcal {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(\mathcal {A}), L(\mathcal {B}))\).

MSC:

03D05 Automata and formal grammars in connection with logical questions
03E15 Descriptive set theory
03E60 Determinacy principles
91A44 Games involving topology, set theory, or logic
PDF BibTeX XML Cite
Full Text: DOI Euclid