Strong bisimilarity and regularity of basic parallel processes is PSPACE-hard

DOI10.1007/3-540-45841-7_44MaRDI QIDQ4736869zbMATH OpenFDO

Authors Jiří Srba

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/2285/22850535.htm

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

• Strong bisimilarity and regularity of basic process algebra is PSPACE-hard
• Decidability of weak bisimilarity for a subset of basic parallel processes
• Approximating weak bisimilarity of basic parallel processes
• On the complexity of bisimulation problems for basic parallel processes
• More on Weak Bisimilarity of Normed Basic Parallel Processes
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• scientific article; zbMATH DE number 1232246
• Bisimilarity of one-counter processes is PSPACE-complete
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• Bisimilarity on basic parallel processes

Cited in

(18)

• Reachability is decidable for weakly extended process rewrite systems
• Non-interleaving bisimulation equivalences on basic parallel processes
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• Complexity of deciding bisimilarity between normed BPA and normed BPP
• Bisimilarity on basic parallel processes
• Decidability of branching bisimulation on normed commutative context-free processes
• Decidability of performance equivalence for basic parallel processes
• On the complexity of bisimulation problems for basic parallel processes
• Decidability of branching bisimulation on normed commutative context-free processes
• Causality, behavioural equivalences, and the security of cyberphysical systems
• More on Weak Bisimilarity of Normed Basic Parallel Processes
• Normed BPA vs. Normed BPP Revisited
• scientific article; zbMATH DE number 1232246 (Why is no real title available?)
• Strong bisimilarity and regularity of basic process algebra is PSPACE-hard
• Undecidability of performance equivalence of Petri nets
• Two lower bounds for BPA
• Weighted basic parallel processes and combinatorial enumeration
• On the computational complexity of bisimulation, redux

This page was built for publication: Strong bisimilarity and regularity of basic parallel processes is PSPACE-hard

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