A hierarchy of deterministic context-free \(\omega\)-languages.

DOI10.1016/S0304-3975(02)00567-4zbMath1044.68090MaRDI QIDQ1401159

Jacques Duparc

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Wadge hierarchyDeterministic context-free \(\omega\)-languagesPushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.