Superdeterministic DPDAs: The method of accepting does affect decision problems

DOI10.1016/0022-0000(79)90015-1MaRDI QIDQ1132642zbMATH OpenOpenAlexFDO

Authors 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

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Cites work

• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 3513357 (Why is no real title available?)
• A direct algorithm for checking equivalence of LL(k) grammars
• A result on the equivalence problem for deterministic pushdown automata
• A variant of a recursively unsolvable problem
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Characteristic and ultrarealtime languages
• Deterministic context free languages
• Deterministic one-counter automata
• Deterministic stack automata and the quotient operator
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• On equivalence of grammars through transformation trees
• One-way stack automata
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• Simple context-free languages and free monadic recursion schemes
• Some remarks on the KH algorithm fors-grammars
• Superdeterministic PDAs
• 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
• The equivalence problem for real-time strict deterministic languages
• The inclusion problem for simple languages
• Two decidability results for deterministic pushdown automata

Cited in

(11)

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

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

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