Borel hierarchy and omega context free languages.

DOI10.1016/S0304-3975(02)00042-7zbMath1051.68094OpenAlexW1621948069MaRDI QIDQ1401165

Olivier Finkel

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00042-7

zbMATH Keywords

Borel hierarchyTopological complexityAnalytic setsContext free \(\omega\)-languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive set theory (03E15) Automata and formal grammars in connection with logical questions (03D05)

Related Items (16)

On omega context free languages which are Borel sets of infinite rank. ⋮ Solving Infinite Games in the Baire Space ⋮ Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words ⋮ The Wadge Hierarchy of Petri Nets ω-Languages ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ Ambiguity in omega context free languages ⋮ 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 ⋮ Classical and effective descriptive complexities of \(\omega \)-powers ⋮ On some sets of dictionaries whose ω -powers have a given ⋮ Topological properties of omega context-free languages ⋮ Wadge hierarchy of omega context-free languages ⋮ Highly Undecidable Problems For Infinite Computations ⋮ Locally finite ω-languages and effective analytic sets have the same topological complexity ⋮ ω-powers and descriptive set theory ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Cites Work

• 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
• 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
• The Borel hierarchy is infinite in the class of regular sets of trees
• \(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.
• Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
• Weak Second‐Order Arithmetic and Finite Automata
• On ω-regular sets
• PUSHDOWN AUTOMATA ON INFINITE TREES AND NONDETERMINISTIC CONTEXT-FREE PROGRAMS
• 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
• 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
• Wadge hierarchy of omega context-free languages

This page was built for publication: Borel hierarchy and omega context free languages.