Superdeterministic DPDAs: The method of accepting does affect decision problems

DOI10.1016/0022-0000(79)90015-1zbMath0419.68100OpenAlexW1980915723MaRDI QIDQ1132642

Sheila A. Greibach, Emily P. Friedman

Publication date: 1979

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(79)90015-1

zbMATH Keywords

acceptance by final state and empty storedecidability of equivalence and inclusionfinite delay automatasuper-deterministic pushdown automata

Mathematics Subject Classification ID

Related Items (11)

On some decision questions concerning pushdown machines ⋮ The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine ⋮ On the decidability of equivalence for deterministic pushdown transducers ⋮ DPDA's in 'Atomic normal form' and applications to equivalence problems ⋮ The inclusion problem for some subclasses of context-free languages ⋮ Monoid-Based Approach to the Inclusion Problem on Superdeterministic Pushdown Automata ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars ⋮ New families of non real time dpda's and their decidability results ⋮ Some results on subclass containment problems for special classes of dpda's related to nonsingular machines ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Deterministic one-counter automata
• A result on the equivalence problem for deterministic pushdown automata
• The inclusion problem for simple languages
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• A direct algorithm for checking equivalence of LL(k) grammars
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Two decidability results for deterministic pushdown automata
• On equivalence of grammars through transformation trees
• Deterministic stack automata and the quotient operator
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• The equivalence problem for real-time strict deterministic languages
• Superdeterministic PDAs
• Some remarks on the KH algorithm fors-grammars
• Simple context-free languages and free monadic recursion schemes
• Tape bounds for some subclasses of deterministic context-free languages
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• Deterministic context free languages
• One-way stack automata
• Characteristic and ultrarealtime languages
• A variant of a recursively unsolvable problem

This page was built for publication: Superdeterministic DPDAs: The method of accepting does affect decision problems