Wadge Degrees ofω-Languages of Deterministic Turing Machines

DOI10.1051/ita:2003008zbMath1048.03031OpenAlexW2146328638MaRDI QIDQ4462679

Victor L. Selivanov

Publication date: 18 May 2004

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2003__37_1_67_0

zbMATH Keywords

Borel setTuring machineWadge hierarchy\(\omega\)-languageWadge degree

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive set theory (03E15) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Hierarchies of computability and definability (03D55)

Related Items

The Hausdorff-Ershov hierarchy in Euclidean spaces, The Wadge Hierarchy of Petri Nets ω-Languages, Infinite games specified by 2-tape automata, Towards a descriptive set theory for domain-like structures, Towards the Effective Descriptive Set Theory, On the High Complexity of Petri Nets $$\omega $$-Languages, Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces, On the main scientific achievements of Victor Selivanov, Extending Wagner's hierarchy to deterministic visibly pushdown automata, Hierarchies of function classes defined by the first-value operator, Unnamed Item, FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES, Fine hierarchies and m-reducibilities in theoretical computer science, On the Difference Hierarchy in Countably Based T0-Spaces, Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization, Wadge hardness in Scott spaces and its effectivization, Polishness of some topologies related to word or tree automata, Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata, On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hierarchies of hyperarithmetical sets and functions
• Fine hierarchy of regular \(\omega\)-languages
• Descriptive set theory
• A hierarchy of deterministic context-free \(\omega\)-languages.
• On ω-regular sets
• Determinateness and the separation property
• Fine hierarchies and Boolean terms