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

SRBA, Jiří. Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard. In Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02). Netherlands: Springer-Verlag, 2002, s. 716-727.

Základní údaje

Originální název

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

Autoři

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

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í

Kód RIV

RIV/00216224:14330/02:00007147

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

bisimilarity checking; complexity; infinite systems

Štítky

bisimilarity checking, complexity, infinite systems

---

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ů