A fast algorithm to decide on the equivalence of stateless DPDA

DOI10.1051/ITA/1993270100231MaRDI QIDQ5286053zbMATH OpenOpenAlexFDO

Authors Didier Caucal

Publication date 29 June 1993

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92436

zbMATH Keywords

equivalencestateless DPDA

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Decidability of DPDA equivalence
• scientific article; zbMATH DE number 2081092
• scientific article; zbMATH DE number 2086674
• The equivalence problem for real-time DPDAs
• An intermediate machine technique for deciding equivalence between a DPDA and a linear DPDA
• scientific article; zbMATH DE number 1738657
• scientific article; zbMATH DE number 2038732
• A weaker sufficient condition for the equivalence of a pair of DPDA's to be decidable
• Algorithm for establishing the equivalence of deterministic multitape automata

Cites work

• scientific article; zbMATH DE number 4155910 (Why is no real title available?)
• scientific article; zbMATH DE number 3958760 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• A direct algorithm for checking equivalence of LL(k) grammars
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
• Completeness results for the equivalence of recursive schemas
• Deterministic one-counter automata
• On equivalence of grammars through transformation trees
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata

Cited in

(7)

• Complete formal systems for equivalence problems
• Equivalence of simple functions
• An intermediate machine technique for deciding equivalence between a DPDA and a linear DPDA
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Infinite results
• Decidability results in automata and process theory
• Pushdown automata, multiset automata, and Petri nets

This page was built for publication: A fast algorithm to decide on the equivalence of stateless DPDA

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