文章基本信息

标题：Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds
本地全文：下载
作者：Jirí Srba
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2002
卷号：9
期号：16
出版社：Aarhus University
摘要：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.