The equivalence problem for deterministic pushdown automata is decidable

DOI10.1007/3-540-63165-8_221zbMath1401.68168OpenAlexW1518704718WikidataQ57381972 ScholiaQ57381972MaRDI QIDQ4571996

Géraud Sénizergues

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Decidability of theories and sets of sentences (03B25)

Related Items

From Security Protocols to Pushdown Automata ⋮ The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Unnamed Item ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ The different shades of infinite session types ⋮ Unnamed Item ⋮ Equivalence of deterministic pushdown automata revisited ⋮ Deciding the Bisimilarity of Context-Free Session Types ⋮ Some properties of iterated languages ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Decidability of DPDA equivalence ⋮ Pushdown automata, multiset automata, and Petri nets ⋮ Periodic properties of pushdown automata ⋮ Deterministic finite automata with recursive calls and DPDAs ⋮ Complete formal systems for equivalence problems ⋮ Frontier between decidability and undecidability: A survey ⋮ On composition and lookahead delegation of \(e\)-services modeled by automata ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Decidability of bisimilarity for one-counter processes. ⋮ \(L(A)=L(B)\)? A simplified decidability proof.

Cites Work

• Unnamed Item
• Unnamed Item
• Deterministic one-counter automata
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• On equivalence of grammars through transformation trees
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• The equivalence problem for real-time DPDAs
• The equivalence problem for deterministic finite-turn pushdown automata
• Deterministic context free languages
• Decidability of bisimulation equivalence for normed pushdown processes