Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

SRBA Jiří

Year of publication 2003
Type Article in Periodical
Magazine / Source Acta Informatica
MU Faculty or unit

Faculty of Informatics

Citation
Web http://www.brics.dk/~srba/publ.html
Field Informatics
Keywords infinite-state systems; bisimilarity; complexity
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info