Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

SRBA Jiří

Rok publikování 2003
Druh Článek v odborném periodiku
Časopis / Zdroj Acta Informatica
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://www.brics.dk/~srba/publ.html
Obor Informatika
Klíčová slova infinite-state systems; bisimilarity; complexity
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.