A fast algorithm to decide on the equivalence of stateless DPDA
From MaRDI portal
Publication:5286053
DOI10.1051/ITA/1993270100231zbMATH Open0778.68051OpenAlexW61385686MaRDI QIDQ5286053FDOQ5286053
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
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
- Title not available (Why is that?)
- A direct algorithm for checking equivalence of LL(k) grammars
- The equivalence problem for deterministic finite-turn pushdown automata
- Deterministic one-counter automata
- The decidability of equivalence for deterministic stateless pushdown automata
- On equivalence of grammars through transformation trees
- An axiomatic approach to the Korenjak-Hopcroft algorithms
- An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
- Title not available (Why is that?)
- Completeness results for the equivalence of recursive schemas
- Title not available (Why is that?)
Cited In (7)
- Decidability results in automata and process theory
- A polynomial algorithm for deciding bisimilarity of normed context-free processes
- Pushdown automata, multiset automata, and Petri nets
- Infinite results
- Complete formal systems for equivalence problems
- Equivalence of simple functions
- An intermediate machine technique for deciding equivalence between a DPDA and a linear DPDA
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)
