Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds

In this paper we study bisimilarity problems for simple process algebras. In particular, we show PSPACE-hardness of the following problems:strong bisimilarity of Basic Parallel Processes (BPP),strong bisimilarity of Basic Process Algebra (BPA),strong regularity of BPP, andstrong regularity of BPA.We also demonstrate NL-hardness of strong regularity problems for the normed subclasses of BPP and BPA. Bisimilarity problems for simple process algebras are introduced in a general framework of process rewrite systems, and a uniform description of the new techniques used for the hardness proofs is provided