Ambiguity in omega context free languages

DOI10.1016/S0304-3975(02)00584-4zbMath1023.68061OpenAlexW1980874421MaRDI QIDQ1399989

Olivier Finkel

Publication date: 30 July 2003

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

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

zbMATH Keywords

languageambiguityBorel hierarchyhierarchy\(\omega\)-languagecontext freewadge

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Highly Undecidable Problems For Infinite Computations ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rational \(\omega\)-languages are non-ambiguous
• Analytic models and ambiguity of context-free languages
• Fine hierarchy of regular \(\omega\)-languages
• Descriptive set theory
• Adherences of languages
• \(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
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• A hierarchy of deterministic context-free \(\omega\)-languages.
• Borel hierarchy and omega context free languages.
• On omega context free languages which are Borel sets of infinite rank.
• 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
• Ambiguity in context free languages
• A Direct Proof of the Inherent Ambiguity of a Simple Context-Free Language
• 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
• Topological properties of omega context-free languages
• Wadge hierarchy of omega context-free languages