The equivalence problem for deterministic pushdown automata is decidable
From MaRDI portal
Publication:4571996
DOI10.1007/3-540-63165-8_221zbMath1401.68168WikidataQ57381972 ScholiaQ57381972MaRDI QIDQ4571996
Publication date: 4 July 2018
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-63165-8_221
68Q45: Formal languages and automata
68Q70: Algebraic theory of languages and automata
03B25: Decidability of theories and sets of sentences
Related Items
Decidability of DPDA equivalence, Pushdown automata, multiset automata, and Petri nets, Deterministic finite automata with recursive calls and DPDAs, A polynomial algorithm testing partial confluence of basic semi-Thue systems, Complete formal systems for equivalence problems, Frontier between decidability and undecidability: A survey, \(L(A)=L(B)\)? decidability results from complete formal systems, \(L(A)=L(B)\)? A simplified decidability proof., Decidability of bisimilarity for one-counter processes., Equivalence of deterministic pushdown automata revisited, On composition and lookahead delegation of \(e\)-services modeled by automata