. "Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds"@cs . . "RIV/00216224:14330/03:00008470" . "Srba, Ji\u0159\u00ED" . . "Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds" . "1" . "Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds" . . "NL - Nizozemsko" . "Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds"@en . "31"^^ . . . "629155" . . "Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds"@en . "Acta Informatica" . "[2041EE904F06]" . "Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds"@cs . "P(GA201/03/1161), Z(MSM 143300001)" . "We study bisimilarity and regularity problems of simple process algebras. In particular, we show PSPACE-hardness of the following problems: (i) strong bisimilarity of Basic Parallel Processes (BPP), (ii) strong bisimilarity of Basic Process Algebra (BPA), (iii) strong regularity of BPP, and (iv) strong regularity of BPA. We also demonstrate NL-hardness of strong regularity problems for the normed subclasses of BPP and BPA. Bisimilarity problems of 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." . . "RIV/00216224:14330/03:00008470!RIV08-MSM-14330___" . "We study bisimilarity and regularity problems of simple process algebras. In particular, we show PSPACE-hardness of the following problems: (i) strong bisimilarity of Basic Parallel Processes (BPP), (ii) strong bisimilarity of Basic Process Algebra (BPA), (iii) strong regularity of BPP, and (iv) strong regularity of BPA. We also demonstrate NL-hardness of strong regularity problems for the normed subclasses of BPP and BPA. Bisimilarity problems of 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."@en . . "1"^^ . "39" . "469-499" . . . . "14330" . . "We study bisimilarity and regularity problems of simple process algebras. In particular, we show PSPACE-hardness of the following problems: (i) strong bisimilarity of Basic Parallel Processes (BPP), (ii) strong bisimilarity of Basic Process Algebra (BPA), (iii) strong regularity of BPP, and (iv) strong regularity of BPA. We also demonstrate NL-hardness of strong regularity problems for the normed subclasses of BPP and BPA. Bisimilarity problems of 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."@cs . . . "1"^^ . . "infinite-state systems; bisimilarity; complexity"@en . .