摘要：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, and strong 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.
