On the complexity of bisimulation problems for pushdown automata

DOI10.1007/3-540-44929-9_33MaRDI QIDQ4536443zbMATH OpenFDO

Authors Richard M. Mayr

Publication date 25 November 2002

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

Full work available at URL https://doi.org/10.1007/3-540-44929-9_33

zbMATH Keywords

bisimulationcomplexitypushdown automataverification

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Bisimilarity of pushdown automata is nonelementary
• scientific article; zbMATH DE number 1929958
• Bisimilarity of probabilistic pushdown automata
• Completeness results for undecidable bisimilarity problems
• On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two

Cited in

(15)

• The complexity of bisimilarity-checking for one-counter processes.
• Simulation preorder over simple process algebras
• A general approach to comparing infinite-state systems with their finite-state specifications
• Completeness results for undecidable bisimilarity problems
• On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• scientific article; zbMATH DE number 1929958 (Why is no real title available?)
• On The Space Complexity Of Turn Bounded Pushdown Automata
• Bisimulation Finiteness of Pushdown Systems Is Elementary
• Bisimilarity of pushdown automata is nonelementary
• On the parallel complexity of bisimulation on finite systems
• Pushdown Automata and Context-Free Grammars in Bisimulation Semantics
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• On the computational complexity of bisimulation, redux
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes

This page was built for publication: On the complexity of bisimulation problems for pushdown automata

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