scientific article; zbMATH DE number 2081092

MaRDI QIDQ4474205zbMATH OpenFDO

Authors Colin Stirling

Publication date 4 August 2004

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

zbMATH Keywords

decidabilityprocess calculuslanguage equivalencebisimulation equivalencedeterministic pushdown automatondeterministic tableau proof decision procedure

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Decidability of DPDA language equivalence via first-order grammars
• scientific article; zbMATH DE number 2086674
• Decidability of DPDA equivalence
• Equivalences of Pushdown Systems Are Hard
• The equivalence problem for deterministic pushdown automata is decidable

Cited in

(18)

• scientific article; zbMATH DE number 2086674 (Why is no real title available?)
• The equivalence problem for deterministic pushdown automata is decidable
• A fast algorithm to decide on the equivalence of stateless DPDA
• Decidability of DPDA equivalence
• scientific article; zbMATH DE number 4083010 (Why is no real title available?)
• Simplification problems for deterministic pushdown automata on infinite words
• Automata, Languages and Programming
• The Hoare logic of deterministic and nondeterministic monadic recursion schemes
• An intermediate machine technique for deciding equivalence between a DPDA and a linear DPDA
• scientific article; zbMATH DE number 1670473 (Why is no real title available?)
• Deterministic Algorithms, Simple Languages And One‐to‐One Gentzen Type Formalizations
• scientific article; zbMATH DE number 1738657 (Why is no real title available?)
• Decidable subcases of the equivalence problem for recursive program schemes
• On the decidability of the PVD class with equality
• New families of non real time dpda's and their decidability results
• Some negative results concerning DPDA's
• A weaker sufficient condition for the equivalence of a pair of DPDA's to be decidable
• Decidability of DPDA language equivalence via first-order grammars

This page was built for publication:

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