Wadge degrees of infinitary rational relations

DOI10.1007/S11786-008-0045-7MaRDI QIDQ1001349zbMATH OpenOpenAlexFDO

Authors Olivier Finkel

Publication date 17 February 2009

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.3266, https://hal-ens-lyon.archives-ouvertes.fr/ensl-00274931/file/Wadge-degrees-rat-relations.pdf

zbMATH Keywords

2-tape Büchi automataBorel hierarchyCantor topologycomplete setsinfinitary rational relationstopological complexityWadge degreesWadge gamesWadge hierarchy

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Descriptive set theory (03E15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: We show that, from the topological point of view, 2-tape B"uchi automata have the same accepting power as Turing machines equipped with a B"uchi acceptance condition. The Borel and the Wadge hierarchies of the class RAT_omega of infinitary rational relations accepted by 2-tape B"uchi automata are equal to the Borel and the Wadge hierarchies of omega-languages accepted by real-time B"uchi 1-counter automata or by B"uchi Turing machines. In particular, for every non-null recursive ordinal $alpha$, there exist some $Sigm{a}_a^{0}lpha$-complete and some $P{i}_a^{0}lpha$-complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal $gamm{a}_2^1$ which is strictly greater than the first non-recursive ordinal $omeg{a}_1^{CK}$. This very surprising result gives answers to questions of Simonnet (1992) and of Lescow and Thomas (1988,1994).

Recommendations

• On the Accepting Power of 2-Tape Büchi Automata
• Borel ranks and Wadge degrees of context free \omega-languages
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• scientific article; zbMATH DE number 1962805
• Infinite games specified by 2-tape automata

Cited in

(12)

• Wadge-Wagner hierarchies
• scientific article; zbMATH DE number 6010989 (Why is no real title available?)
• Infinite games specified by 2-tape automata
• The Wadge hierarchy of Petri nets \(\omega\)-languages
• scientific article; zbMATH DE number 2040947 (Why is no real title available?)
• The Wadge-Wagner hierarchy of ω-rational sets
• Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• Wadge-like degrees of Borel bqo-valued functions
• On the high complexity of Petri nets -languages
• On the Accepting Power of 2-Tape Büchi Automata
• Relations rationnelles infinitaires

This page was built for publication: Wadge degrees of infinitary rational relations

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