A decidability result for deterministic \(\omega\)-context-free languages

DOI10.1016/0304-3975(77)90058-5zbMath0357.68076OpenAlexW2043998485MaRDI QIDQ1239008

Matti Linna

Publication date: 1977

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

Full work available at URL: https://doi.org/10.1016/0304-3975(77)90058-5

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On omega context free languages which are Borel sets of infinite rank. ⋮ On the complexity of \(\omega\)-type Turing acceptors ⋮ Ambiguity in omega context free languages ⋮ Borel hierarchy and omega context free languages. ⋮ \(X\)-automata on \(\omega\)-words ⋮ Topological properties of omega context-free languages ⋮ Wadge hierarchy of omega context-free languages ⋮ \(\omega\)-computations on deterministic pushdown machines ⋮ Simplification Problems for Deterministic Pushdown Automata on Infinite Words ⋮ Separately continuous algebras

Cites Work

• Theories of automata on \(\omega\)-tapes: a simplified approach
• On ω-sets associated with context-free languages
• Deterministic context free languages
• Decision problems forω-automata
• Testing and generating infinite sequences by a finite automaton
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item