Nondeterministic Ω-Computations and the Analytical Hierarchy

DOI10.1002/MALQ.19890350406zbMATH Open0661.03030OpenAlexW2020658239MaRDI QIDQ3809783FDOQ3809783

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

Recommendations

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

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)

Cited In (11)

• Title not available (Why is that?)
• 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
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• On the high complexity of Petri nets \(\omega \)-languages
• Some problems in automata theory which depend on the models of set theory

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)