Infinite games specified by 2-tape automata

From MaRDI portal
(Redirected from Publication:324245)


DOI10.1016/J.APAL.2016.05.005MaRDI QIDQ324245zbMATH OpenOpenAlexFDO

Authors Olivier Finkel

Publication date 10 October 2016

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

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


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)


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) Aalpha, indexed by recursive ordinals, such that the games G(L(Aalpha)) 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.


Recommendations


Cites work


Cited in
(8)






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)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Infinite_games_specified_by_2-tape_automata&oldid=60964986"
Powered by MediaWiki