Wadge Degrees ofω-Languages of Deterministic Turing Machines

DOI10.1051/ITA:2003008MaRDI QIDQ4462679zbMATH OpenOpenAlexFDO

Authors Victor 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, https://eudml.org/doc/92714

zbMATH Keywords

\(\omega\)-languageBorel setTuring machineWadge degreeWadge hierarchy

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1962805
• New Computational Paradigms
• Borel ranks and Wadge degrees of context free \omega-languages
• On the length of the Wadge hierarchy of -context-free languages
• Ambiguity of -languages of Turing machines
• The determinacy strength of pushdownω-languages
• The \(\omega\)-Turing degrees
• Wadge hierarchy of omega context-free languages
• scientific article; zbMATH DE number 1836415
• scientific article; zbMATH DE number 3990900

Cites work

• A hierarchy of deterministic context-free \(\omega\)-languages.
• Descriptive set theory
• Determinateness and the separation property
• Fine hierarchies and Boolean terms
• Fine hierarchy of regular \(\omega\)-languages
• Hierarchies of hyperarithmetical sets and functions
• scientific article; zbMATH DE number 3849219 (Why is no real title available?)
• scientific article; zbMATH DE number 3609660 (Why is no real title available?)
• scientific article; zbMATH DE number 1962805 (Why is no real title available?)
• scientific article; zbMATH DE number 3264065 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3342831 (Why is no real title available?)
• On ω-regular sets

Cited in

(27)

• Wadge degrees of infinitary rational relations
• \(\Pi_ 2^ 1\) Wadge degrees
• Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank
• Towards the Effective Descriptive Set Theory
• Infinite games specified by 2-tape automata
• Borel ranks and Wadge degrees of context free \omega-languages
• The Wadge hierarchy of Petri nets \(\omega\)-languages
• Hierarchies of function classes defined by the first-value operator
• FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
• On the difference hierarchy in countably based \(T_{0}\)-spaces
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time
• On the high complexity of Petri nets -languages
• The determinacy strength of pushdownω-languages
• Polishness of some topologies related to word or tree automata
• Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization
• Wadge hardness in Scott spaces and its effectivization
• Computer science and the fine structure of Borel sets
• scientific article; zbMATH DE number 7770056 (Why is no real title available?)
• On the main scientific achievements of Victor Selivanov
• Extending Wagner's hierarchy to deterministic visibly pushdown automata
• Iterated priority arguments in descriptive set theory
• The Hausdorff-Ershov hierarchy in Euclidean spaces
• Towards a descriptive set theory for domain-like structures
• Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: Wadge Degrees ofω-Languages of Deterministic Turing Machines

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