Equivalence of deterministic pushdown automata revisited

DOI10.1007/S10559-007-0037-7zbMATH Open1125.68066OpenAlexW2012479020MaRDI QIDQ2458041FDOQ2458041

Authors V. Yu. Meitus

Publication date 31 October 2007

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

Full work available at URL https://doi.org/10.1007/s10559-007-0037-7

zbMATH Keywords

deterministic pushdown automataequivalence problemdecidability of problemsdeterministic CF language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• Decidability of the equivalence problem for deterministic pushdown automata
• The equivalence problem for real-time DPDAs
• Decidability of DPDA equivalence
• The equivalence problem for deterministic pushdown automata is decidable
• scientific article; zbMATH DE number 1232245

Cites work

• scientific article; zbMATH DE number 3310084 (Why is no real title available?)
• Deterministic one-counter automata
• On the translation of languages from left to right
• Properties of deterministic top-down grammars
• Strict deterministic grammars
• The equivalence problem for deterministic finite-turn pushdown automata
• The equivalence problem for deterministic pushdown automata is decidable
• The equivalence problem for real-time DPDAs
• \(L(A)=L(B)\)? decidability results from complete formal systems

Cited in

(17)

• scientific article; zbMATH DE number 2150277 (Why is no real title available?)
• Equivalence of pushdown automata via first-order grammars
• scientific article; zbMATH DE number 4131657 (Why is no real title available?)
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
• A Note on Pushdown Automata Systems
• When input-driven pushdown automata meet reversiblity
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
• Decidability of the equivalence problem for deterministic pushdown automata
• A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict
• scientific article; zbMATH DE number 2163034 (Why is no real title available?)
• scientific article; zbMATH DE number 2086608 (Why is no real title available?)
• Equivalence checking of prefix-free transducers and deterministic two-tape automata
• scientific article; zbMATH DE number 1929958 (Why is no real title available?)
• Equivalences of Pushdown Systems Are Hard
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Variations on pushdown machines (Detailed Abstract)

This page was built for publication: Equivalence of deterministic pushdown automata revisited

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