Strong bisimilarity and regularity of basic process algebra is PSPACE-hard

DOI10.1007/3-540-45465-9_61MaRDI QIDQ4737202zbMATH 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/2380/23800716.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 parallel processes is PSPACE-hard
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• Complexity of Weak Bisimilarity and Regularity for BPA and BPP
• Complexity of weak bisimilarity and regularity for BPA and BPP
• On the complexity of bisimulation problems for basic parallel processes

Cited in

(14)

• The complexity of bisimilarity-checking for one-counter processes.
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• Complexity of deciding bisimilarity between normed BPA and normed BPP
• Bisimulation equivalence and regularity for real-time one-counter automata
• On the complexity of bisimulation problems for basic parallel processes
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• Normed BPA vs. Normed BPP Revisited
• P-hardness of equivalence testing on finite-state processes
• Strong bisimilarity and regularity of basic parallel processes is PSPACE-hard
• Convenient category of processes and simulations I: Modulo strong bisimilarity
• Two lower bounds for BPA
• 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: Strong bisimilarity and regularity of basic process algebra is PSPACE-hard

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