J 2003

Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds

SRBA, Jiří

Basic information

Original name

Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds

Authors

SRBA, Jiří (203 Czech Republic, guarantor)

Edition

Acta Informatica, The Netherlands, Springer-Verlag, 2003

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

RIV identification code

RIV/00216224:14330/03:00008470

Organization unit

Faculty of Informatics

Keywords in English

infinite-state systems; bisimilarity; complexity

Tags

Změněno: 26/5/2004 13:37, Prof. Jiří Srba, Ph.D.

Abstract

V originále

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.

Links

GA201/03/1161, research and development project
Name: Verifikace nekonečně stavových systémů
Investor: Czech Science Foundation, Verification of infinite-state systems
MSM 143300001, plan (intention)
Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing