Infinite games specified by 2-tape automata

DOI10.1016/J.APAL.2016.05.005zbMATH Open1422.03113arXiv1312.3797OpenAlexW2963698523MaRDI QIDQ324245FDOQ324245

Authors: Olivier Finkel 

Publication date: 10 October 2016

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Abstract: We prove that the determinacy of Gale-Stewart games whose winning sets are infinitary rational relations accepted by 2-tape B"uchi 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 B"uchi 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 B"uchi automata (respectively, of real-time 1-counter B"uchi automata) $A_{a}lpha$, indexed by recursive ordinals, such that the games $G(L(A_{a}lpha))$ have strictly increasing strenghs of determinacy. Moreover there is a 2-tape B"uchi automaton (respectively, a real-time 1-counter B"uchi 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 B"uchi automata is equivalent to the (effective) analytic determinacy, and thus not provable in ZFC.

Full work available at URL: https://arxiv.org/abs/1312.3797

Recommendations

• The determinacy strength of pushdownω-languages
• The Complexity of Infinite Computations In Models of Set Theory
• Wadge degrees of infinitary rational relations

zbMATH Keywords

determinacylogic in computer scienceautomata and formal languagesmodels of set theory1-counter automatoncomplexity of winning strategieseffective analytic determinacyGale-Stewart gamesindependence from the axiomatic system ZFCwadge games2-tape Büchi automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive set theory (03E15) Consistency and independence results (03E35) Determinacy principles (03E60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Set theory. An introduction to independence proofs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Infinite Computations In Models of Set Theory
• Wadge reducibility and infinite computations
• Wadge degrees of infinitary rational relations
• \(\omega\)-computations on Turing machines
• Classical recursion theory. Vol. II
• Pushdown processes: Games and model-checking
• Complexity of winning strategies
• Title not available (Why is that?)
• On the topological complexity of tree languages
• Title not available (Why is that?)
• Borel ranks and Wadge degrees of context free $\omega$-languages
• Highly Undecidable Problems For Infinite Computations
• Title not available (Why is that?)
• Nondeterministic Ω-Computations and the Analytical Hierarchy
• Analytic determinacy and 0^#
• Title not available (Why is that?)
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• Title not available (Why is that?)
• On the synthesis of strategies in infinite games
• Title not available (Why is that?)
• Infinite games in the Cantor space and subsystems of second order arithmetic
• On the Accepting Power of 2-Tape Büchi Automata
• Church’s Problem and a Tour through Automata Theory
• Measurable cardinals and analytic games

Cited In (8)

• Effective strategies for enumeration games
• Multitape games
• Title not available (Why is that?)
• Winning strategies for infinite games: from large cardinals to computer science extended abstract
• On the Accepting Power of 2-Tape Büchi Automata
• Wadge degrees of infinitary rational relations
• Title not available (Why is that?)
• Some problems in automata theory which depend on the models of set theory

This page was built for publication: Infinite games specified by 2-tape automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q324245)