The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine

DOI10.1016/0022-0000(81)90072-6zbMath0473.68046OpenAlexW2051999169MaRDI QIDQ1158757

Namio Honda, Yasuyoshi Inagaki, Michio Oyamaguchi

Publication date: 1981

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(81)90072-6

zbMATH Keywords

deterministic pushdown automata

Mathematics Subject Classification ID

Related Items

The extended equivalence problem for a class of non-real-time deterministic pushdown automata, On some decision questions concerning pushdown machines, Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages, Decidable subcases of the equivalence problem for recursive program schemes, 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
• Superdeterministic DPDAs: The method of accepting does affect decision problems
• Deterministic one-counter automata
• A result on the equivalence problem for deterministic pushdown automata
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• On equivalence and subclass containment problems for deterministic context-free languages
• Two decidability results for deterministic pushdown automata
• On equivalence of grammars through transformation trees
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• The equivalence problem for real-time strict deterministic languages
• The equivalence problem for some non-real-time deterministic pushdown automata
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• Deterministic context free languages
• Properties of deterministic top-down grammars
• Real-Time Strict Deterministic Languages