\(\omega\)-computations on deterministic pushdown machines

DOI10.1016/0022-0000(78)90019-3zbMath0382.03025OpenAlexW2038722538MaRDI QIDQ1247962

Arie Y. Gold, Rina S. Cohen

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90019-3

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35) Automata and formal grammars in connection with logical questions (03D05)

Related Items

On omega context free languages which are Borel sets of infinite rank. ⋮ Somewhat finite approaches to infinite sentences. ⋮ On the complexity of \(\omega\)-type Turing acceptors ⋮ Ambiguity in omega context free languages ⋮ A hierarchy of deterministic context-free \(\omega\)-languages. ⋮ Borel hierarchy and omega context free languages. ⋮ Model checking probabilistic systems against pushdown specifications ⋮ Unnamed Item ⋮ Valuations of languages, with applications to fractal geometry ⋮ Distributed synthesis for regular and contextfree specifications ⋮ \(X\)-automata on \(\omega\)-words ⋮ Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages ⋮ Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition ⋮ Topological properties of omega context-free languages ⋮ Wadge hierarchy of omega context-free languages ⋮ \(\omega\)-computations on Turing machines ⋮ Highly Undecidable Problems For Infinite Computations ⋮ Real functions and numbers defined by Turing machines ⋮ Finite-state \(\omega\)-languages ⋮ Init and Anf operating on \(\omega\)-languages ⋮ Alternating finite automata on \(\omega\)-words ⋮ The exact complexity of the infinite Post Correspondence Problem ⋮ Games with winning conditions of high Borel complexity

Cites Work

• Theories of automata on \(\omega\)-tapes: a simplified approach
• A decidability result for deterministic \(\omega\)-context-free languages
• Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
• Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
• Strict deterministic grammars
• Deterministic context free languages
• A regularity test for pushdown machines
• Decision problems forω-automata
• Testing and generating infinite sequences by a finite automaton
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item