Decidability of the equivalence problem for deterministic pushdown automata

DOI10.1007/BF01131845zbMath0875.68644MaRDI QIDQ1816326

V. Yu. Mejtus

Publication date: 20 January 1997

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

zbMATH Keywords

decidabilitydeterministic pushdown automataequivalence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65)

Related Items (1)

\(L(A)=L(B)\)? decidability results from complete formal systems

Cites Work

• Unnamed Item
• 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
• Program schemes, recursion schemes, and formal languages
• The equivalence problem for deterministic finite-turn pushdown automata
• Deterministic context free languages
• Properties of deterministic top-down grammars
• On the translation of languages from left to right

This page was built for publication: Decidability of the equivalence problem for deterministic pushdown automata