A fast algorithm to decide on the equivalence of stateless DPDA

DOI10.1051/ita/1993270100231zbMath0778.68051OpenAlexW61385686MaRDI QIDQ5286053

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)

Related Items

A polynomial algorithm for deciding bisimilarity of normed context-free processes, Equivalence of simple functions, Infinite results, Pushdown automata, multiset automata, and Petri nets, Complete formal systems for equivalence problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
• Deterministic one-counter automata
• Completeness results for the equivalence of recursive schemas
• A direct algorithm for checking equivalence of LL(k) grammars
• On equivalence of grammars through transformation trees
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata