Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Determinacy of Context-Free Games
244
0
0.0
(
0
)
Added by
Olivier Finkel
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Olivier Finkel
Ask ChatGPT about the research
No Arabic abstract
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Buchi 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 Buchi 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 Buchi automaton A and a Buchi 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)).
rate research
Read More
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Buchi 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 Buchi 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 Buchi automaton A and a Buchi 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)).
We show that, from a topological point of view, considering the Borel and the Wadge hierarchies, 1-counter Buchi automata have the same accepting power than Turing machines equipped with a Buchi acceptance condition. In particular, for every non null recursive ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete omega context free languages accepted by 1-counter Buchi automata, and the supremum of the set of Borel ranks of context free omega languages is the ordinal gamma^1_2 which is strictly greater than the first non recursive ordinal. This very surprising result gives answers to questions of H. Lescow and W. Thomas [Logical Specifications of Infinite Computations, In:A Decade of Concurrency, LNCS 803, Springer, 1994, p. 583-621].
We prove that the determinacy of Gale-Stewart games whose winning sets are infinitary rational relations accepted by 2-tape Buchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. Then we prove that winning strategies, when they exist, can be very complex, i.e. highly non-effective, in these games. We prove the same results for Gale-Stewart games with winning sets accepted by real-time 1-counter Buchi automata, then extending previous results obtained about these games. Then we consider the strenghs of determinacy for these games, and we prove that there is a transfinite sequence of 2-tape Buchi automata (respectively, of real-time 1-counter Buchi automata) $A_alpha$, indexed by recursive ordinals, such that the games $G(L(A_alpha))$ have strictly increasing strenghs of determinacy. Moreover there is a 2-tape Buchi automaton (respectively, a real-time 1-counter Buchi automaton) B such that the determinacy of G(L(B)) is equivalent to the (effective) analytic determinacy and thus has the maximal strength of determinacy. We show also that the determinacy of Wadge games between two players in charge of infinitary rational relations accepted by 2-tape Buchi automata is equivalent to the (effective) analytic determinacy, and thus not provable in ZFC.
Some decidable winning conditions of arbitrarily high finite Borel complexity for games on finite graphs or on pushdown graphs have been recently presented by O. Serre in [ Games with Winning Conditions of High Borel Complexity, in the Proceedings of the International Conference ICALP 2004, LNCS, Volume 3142, p. 1150-1162 ]. We answer in this paper several questions which were raised by Serre in the above cited paper. We first show that, for every positive integer n, the class C_n(A), which arises in the definition of decidable winning conditions, is included in the class of non-ambiguous context free omega languages, and that it is neither closed under union nor under intersection. We prove also that there exists pushdown games, equipped with such decidable winning conditions, where the winning sets are not deterministic context free languages, giving examples of winning sets which are non-deterministic non-ambiguous context free languages, inherently ambiguous context free languages, or even non context free languages.
We survey recent results on the topological complexity of context-free omega-languages which form the second level of the Chomsky hierarchy of languages of infinite words. In particular, we consider the Borel hierarchy and the Wadge hierarchy of non-deterministic or deterministic context-free omega-languages. We study also decision problems, the links with the notions of ambiguity and of degrees of ambiguity, and the special case of omega-powers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
