A hierarchy of deterministic context-free \(\omega\)-languages.
From MaRDI portal
Publication:1401159
DOI10.1016/S0304-3975(02)00567-4zbMath1044.68090MaRDI QIDQ1401159
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (20)
On omega context free languages which are Borel sets of infinite rank. ⋮ The Wadge Hierarchy of Petri Nets ω-Languages ⋮ Towards a descriptive set theory for domain-like structures ⋮ A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ Ambiguity in omega context free languages ⋮ Borel hierarchy and omega context free languages. ⋮ Extending Wagner's hierarchy to deterministic visibly pushdown automata ⋮ Unnamed Item ⋮ FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Baire reductions and good Borel reducibilities ⋮ Topological properties of omega context-free languages ⋮ Wadge hierarchy of omega context-free languages ⋮ Wadge Degrees ofω-Languages of Deterministic Turing Machines ⋮ 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 ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words ⋮ Input-driven pushdown automata on well-nested infinite strings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Descriptive set theory
- Borel determinacy
- Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
- \(\omega\)-computations on deterministic pushdown machines
- Topology and descriptive set theory
- Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
- On ω-regular sets
- Separation principles and the axiom of determinateness
- Deterministic context free languages
- Solving Sequential Conditions by Finite-State Strategies
- Computer science and the fine structure of Borel sets
- Topological properties of omega context-free languages
This page was built for publication: A hierarchy of deterministic context-free \(\omega\)-languages.