-computations on deterministic pushdown machines

DOI10.1016/0022-0000(78)90019-3zbMATH Open0382.03025OpenAlexW2038722538MaRDI QIDQ1247962FDOQ1247962

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

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

Cited In (23)

• Topological properties of omega context-free languages
• Model checking probabilistic systems against pushdown specifications
• 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
• Title not available (Why is that?)
• \(X\)-automata on \(\omega\)-words
• Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
• Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
• Alternating finite automata on \(\omega\)-words
• Finite-state \(\omega\)-languages
• Distributed synthesis for regular and contextfree specifications
• \(\omega\)-computations on Turing machines
• Real functions and numbers defined by Turing machines
• On the complexity of \(\omega\)-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)