D 2002

Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard

SRBA, Jiří

Základní údaje

Originální název

Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard

Autoři

SRBA, Jiří

Vydání

Netherlands, Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02), s. 716-727, 2002

Nakladatel

Springer-Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10000 1. Natural Sciences

Stát vydavatele

Nizozemské království

Utajení

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

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/02:00007147

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

bisimilarity checking; complexity; infinite systems

Štítky

Změněno: 21. 5. 2003 09:46, Prof. Jiří Srba, Ph.D.

Anotace

V originále

Strong bisimilarity and regularity checking problems of Basic Process Algebra (BPA) are decidable, with the complexity upper bounds 2-EXPTIME. On the other hand, no lower bounds were known. In this paper we demonstrate PSPACE-hardness of these problems.

Návaznosti

GA201/00/0400, projekt VaV
Název: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Nekonečně stavové souběžné systémy - modely a verifikace
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ů