-computations on deterministic pushdown machines

DOI10.1016/0022-0000(78)90019-3MaRDI QIDQ1247962zbMATH OpenOpenAlexFDO

Authors Rina S. Cohen, Arie Y. Gold

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) Automata and formal grammars in connection with logical questions (03D05) Undecidability and degrees of sets of sentences (03D35)

Cites work

• scientific article; zbMATH DE number 3427224 (Why is no real title available?)
• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3564366 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A decidability result for deterministic \(\omega\)-context-free languages
• A regularity test for pushdown machines
• Decision problems forω-automata
• Deterministic context free languages
• Strict deterministic grammars
• Testing and generating infinite sequences by a finite automaton
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Theory of -languages. I: Characterizations of -context- free languages
• Theory of -languages. II: A study of various models of - type generation and recognition

Cited in

(23)

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

This page was built for publication: \(\omega\)-computations on deterministic pushdown machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1247962)