Topological properties of omega context-free languages
From MaRDI portal
Publication:5958141
DOI10.1016/S0304-3975(00)00405-9zbMath0992.68125OpenAlexW2087879437MaRDI QIDQ5958141
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00405-9
topological propertiesarithmetical propertiesBorel classdecide the Borel classGale-Stewart gameomega context-free languagesomega powersWadge class
Related Items (21)
On omega context free languages which are Borel sets of infinite rank. ⋮ The Wadge Hierarchy of Petri Nets ω-Languages ⋮ The Kolmogorov complexity of infinite words ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ Ambiguity in omega context free languages ⋮ A hierarchy of deterministic context-free \(\omega\)-languages. ⋮ Borel hierarchy and omega context free languages. ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ Some subsets of monadic first-order logic (MFO) used for the specification and synthesis of \(\Sigma\)-automata ⋮ Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank ⋮ Unnamed Item ⋮ Topological complexity of locally finite \(\omega\)-languages ⋮ Problems of synthesis of \(\Sigma\)-automata specified in languages LP and LF of first order logic ⋮ Distributed synthesis for regular and contextfree specifications ⋮ Classical and effective descriptive complexities of \(\omega \)-powers ⋮ On some sets of dictionaries whose ω -powers have a given ⋮ Wadge hierarchy of omega context-free languages ⋮ Highly Undecidable Problems For Infinite Computations ⋮ ω-powers and descriptive set theory ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words ⋮ Games with winning conditions of high Borel complexity
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
- A hierarchy of deterministic context-free \(\omega\)-languages.
- Borel hierarchy and omega context free languages.
- Pushdown processes: Games and model-checking
- 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
- On the synthesis of strategies in infinite games
- 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
- Developments in Language Theory
- Computer science and the fine structure of Borel sets
- Wadge hierarchy 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
This page was built for publication: Topological properties of omega context-free languages
