zbMATH — the first resource for mathematics

Complexity of checking bisimilarity between sequential and parallel processes. (English) Zbl 1398.68361
Chatterjee, Krishnendu (ed.) et al., Mathematical foundations of computer science 2013. 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40312-5/pbk). Lecture Notes in Computer Science 8087, 302-313 (2013).
Summary: Decidability of bisimilarity for process algebra (PA) processes, arising by mixing sequential and parallel composition, is a long-standing open problem. The known results for subclasses contain the decidability of bisimilarity between basic sequential (i.e. BPA) processes and basic parallel processes (BPP). Here we revisit this subcase and derive an exponential-time upper bound. Moreover, we show that the problem if a given basic parallel process is inherently sequential, i.e., bisimilar with an unspecified BPA process, is PSPACE-complete. We also introduce a model of one-counter automata, with no zero tests but with counter resets, that capture the behaviour of processes in the intersection of BPA and BPP.
For the entire collection see [Zbl 1270.68020].
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI