Deciding DPDA equivalence is primitive recursive

DOI10.1007/3-540-45465-9_70MaRDI QIDQ4737211zbMATH OpenFDO

Authors Colin Stirling

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2380/23800821.htm

Mathematics Subject Classification ID

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

Recommendations

• An introduction to decidability of DPDA equivalence
• Decidability of the equivalence problem for deterministic pushdown automata
• Decidability of DPDA language equivalence via first-order grammars
• The equivalence problem for deterministic pushdown automata is decidable
• Decidability of the equivalence problem for synchronous deterministic pushdown-store automata

Cited in

(30)

• Deterministic finite automata with recursive calls and DPDAs
• A weaker sufficient condition for the equivalence of a pair of DPDA's to be decidable
• An approach to deciding the observational equivalence of Algol-like languages
• Equivalence of pushdown automata via first-order grammars
• On decision problems for parameterized machines
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• On long words avoiding Zimin patterns
• Trace inclusion for one-counter nets revisited
• Bisimulation equivalence and regularity for real-time one-counter automata
• Schema revisited
• Model-checking games for typed -calculi
• Trace inclusion for one-counter nets revisited
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• An intermediate machine technique for deciding equivalence between a DPDA and a linear DPDA
• Decidable subcases of the equivalence problem for recursive program schemes
• The equivalence problem for real-time DPDAs
• The equivalence problem for t-turn DPDA is co-NP
• An introduction to decidability of DPDA equivalence
• Some applications of the decidability of DPDA's equivalence
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• From security protocols to pushdown automata
• The Hoare logic of deterministic and nondeterministic monadic recursion schemes
• A fast algorithm to decide on the equivalence of stateless DPDA
• Decidability of DPDA equivalence
• System \(F^\mu_\omega\) with context-free session types
• Bisimulation equivalence of pushdown automata is Ackermann-complete
• Equivalence of deterministic weighted real-time one-counter automata
• Weighted one-deterministic-counter automata
• On the computational complexity of bisimulation, redux
• On the universe, disjointness, and containment problems for simple machines

This page was built for publication: Deciding DPDA equivalence is primitive recursive

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