Borel ranks and Wadge degrees of context free $\omega$-languages
From MaRDI portal
Publication:3422021
DOI10.1017/S0960129506005597zbMath1121.03047OpenAlexW2963717725MaRDI QIDQ3422021
Publication date: 9 February 2007
Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0960129506005597
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)
Related Items (19)
Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words ⋮ The Wadge Hierarchy of Petri Nets ω-Languages ⋮ Infinite games specified by 2-tape automata ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ On the continuity set of an Omega rational function ⋮ The expressive power of analog recurrent neural networks on infinite input streams ⋮ Unnamed Item ⋮ On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets ⋮ Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE ⋮ Classical and effective descriptive complexities of \(\omega \)-powers ⋮ Polishness of some topologies related to word or tree automata ⋮ Highly Undecidable Problems For Infinite Computations ⋮ Locally finite ω-languages and effective analytic sets have the same topological complexity ⋮ Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata ⋮ Wadge-Wagner hierarchies ⋮ 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
This page was built for publication: Borel ranks and Wadge degrees of context free $\omega$-languages
