Wadge hierarchy of omega context-free languages
From MaRDI portal
Publication:5958618
DOI10.1016/S0304-3975(01)00008-1zbMath0992.68127MaRDI QIDQ5958618
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Wadge hierarchytopological propertiesomega context-free languagesconciliating Wadge hierarchyinfinitary context-free languagesiterated counter-languages
Related Items (7)
On omega context free languages which are Borel sets of infinite rank. ⋮ The Wadge Hierarchy of Petri Nets ω-Languages ⋮ Ambiguity in omega context free languages ⋮ Borel hierarchy and omega context free languages. ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Topological properties of omega context-free languages ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words
Cites Work
- A classification of \(\omega\)-regular languages
- Fine hierarchy of regular \(\omega\)-languages
- Descriptive set theory
- Adherences of languages
- The Hausdorff-Kuratowski hierarchy of \(\omega\)-regular languages and a hierarchy of Muller automata
- \(X\)-automata on \(\omega\)-words
- The monadic second order theory of all countable ordinals
- A decidability result for deterministic \(\omega\)-context-free languages
- Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
- \(\omega\)-computations on deterministic pushdown machines
- Model theory
- A hierarchy of deterministic context-free \(\omega\)-languages.
- Borel hierarchy and omega context free languages.
- Langages à un compteur
- Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
- Weak Second‐Order Arithmetic and Finite Automata
- On ω-regular sets
- On ω-sets associated with context-free languages
- Chains and Superchains for ω-Rational Sets, Automata and Semigroups
- THE WAGNER HIERARCHY
- Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time
- Solving Sequential Conditions by Finite-State Strategies
- Decision problems forω-automata
- Testing and generating infinite sequences by a finite automaton
- Computer science and the fine structure of Borel sets
- Topological properties of omega context-free languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Wadge hierarchy of omega context-free languages