Nondeterministic Ω-Computations and the Analytical Hierarchy

DOI10.1002/MALQ.19890350406MaRDI QIDQ3809783zbMATH OpenOpenAlexFDO

Authors

Publication date 1989

Published in Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19890350406

zbMATH Keywords

infinite wordscomputabilityanalytical hierarchy\(\omega\)-nondeterministic Turing machinesrecognized languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 4019040
• scientific article; zbMATH DE number 1962805
• Highly Undecidable Problems For Infinite Computations
• scientific article; zbMATH DE number 1836415
• scientific article; zbMATH DE number 3988741

Cited in

(11)

• scientific article; zbMATH DE number 1836415 (Why is no real title available?)
• Highly Undecidable Problems For Infinite Computations
• Decision problems for Turing machines
• Locally finite \(\omega\)-languages and effective analytic sets have the same topological complexity
• Classes of timed automata and the undecidability of universality
• Infinite games specified by 2-tape automata
• On the Herbrand-Kleene universe for nondeterministic computations
• On the complexity of stream equality
• Some problems in automata theory which depend on the models of set theory
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• On the high complexity of Petri nets \(\omega \)-languages

This page was built for publication: Nondeterministic Ω-Computations and the Analytical Hierarchy

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