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

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

zbMATH Keywords

deterministic pushdown automataequivalence problemdecidability of problemsdeterministic CF language

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (17)

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

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)