Nondeterministic Ω-Computations and the Analytical Hierarchy
From MaRDI portal
Publication:3809783
DOI10.1002/malq.19890350406zbMath0661.03030OpenAlexW2020658239MaRDI QIDQ3809783
No author found.
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
computabilityinfinite wordsanalytical hierarchy\(\omega\)-nondeterministic Turing machinesrecognized languages
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (9)
Infinite games specified by 2-tape automata ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ Decision problems for Turing machines ⋮ Highly Undecidable Problems For Infinite Computations ⋮ Locally finite ω-languages and effective analytic sets have the same topological complexity ⋮ Classes of Timed Automata and the Undecidability of Universality ⋮ 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 complexity of stream equality
This page was built for publication: Nondeterministic Ω-Computations and the Analytical Hierarchy
