In: Aarts, E.H.L.: Lecture Notes in Computer Science, Vol. 506; PARLE'91, Vol. 2, Parallel Languages. Proceedings of the Conference on Parallel Architectures and Languages Europe, 1991, Eindhoven, The Netherlands, pages 288-303. Berlin, Germany: Springer, 1991.
Abstract: The authors study the parallel complexity of three problems on concurrency: decision of firing sequences for Petri nets, trace equivalence for partially commutative monoids, and strong bisimilarity in finite transition systems. The authors show that the first two problems can be efficiently parallelized. On the other hand, strong bisimilarity in finite labelled transition systems can be classified as P-complete; as a consequence, algorithms for automated analysis of finite state systems based on bisimulation seem to be inherently sequential.
Keywords: parallel complexity (in) design (and) analysis (of) concurrent system; decision (of) firing sequence; trace equivalence (for) partially commutative monoid; strong bisimilarity (in) finite transition system; finite labelled transition system; bisimulation.