On the complexity of bisimulation problems for basic parallel processes

DOI10.1007/3-540-45022-X_29MaRDI QIDQ2754155zbMATH OpenFDO

Authors Richard M. Mayr

Publication date 11 November 2001

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

Full work available at URL https://doi.org/10.1007/3-540-45022-X_29

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

• Complexity of weak bisimilarity and regularity for BPA and BPP
• Complexity of Weak Bisimilarity and Regularity for BPA and BPP
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• scientific article; zbMATH DE number 2086414
• scientific article; zbMATH DE number 2086665

Cited in

(21)

• Non-interleaving bisimulation equivalences on basic parallel processes
• On reachability equivalence for BPP-nets
• Undecidable problems in unreliable computations.
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• From bisimulation to simulation: Coarsest partition problems
• A complexity analysis of bisimilarity for value-passing processes
• Bisimilarity on basic parallel processes
• Complexity of checking bisimilarity between sequential and parallel processes
• More on Weak Bisimilarity of Normed Basic Parallel Processes
• scientific article; zbMATH DE number 1232246 (Why is no real title available?)
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• scientific article; zbMATH DE number 2086414 (Why is no real title available?)
• scientific article; zbMATH DE number 2086665 (Why is no real title available?)
• scientific article; zbMATH DE number 2102770 (Why is no real title available?)
• Complexity of Weak Bisimilarity and Regularity for BPA and BPP
• Approximating weak bisimilarity of basic parallel processes
• A Study on Team Bisimulations for BPP Nets
• On the parallel complexity of bisimulation on finite systems
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• Weak bisimulation and model checking for basic parallel processes
• On the computational complexity of bisimulation, redux

This page was built for publication: On the complexity of bisimulation problems for basic parallel processes

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