J 2003

Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds

SRBA, Jiří

Základní údaje

Originální název

Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds

Autoři

SRBA, Jiří (203 Česká republika, garant)

Vydání

Acta Informatica, The Netherlands, Springer-Verlag, 2003

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

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

Odkazy

Kód RIV

RIV/00216224:14330/03:00008470

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

infinite-state systems; bisimilarity; complexity

Štítky

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

Anotace

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.

Návaznosti

GA201/03/1161, projekt VaV
Název: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů
MSM 143300001, záměr
Název: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů