Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard

SRBA, Jiří. Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard. In Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02). Holland: Springer-Verlag, 2002, s. 535-546.

Základní údaje

Originální název

Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard

Autoři

SRBA, Jiří

Vydání

Holland, Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02), s. 535-546, 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:00005680

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

We show that the problem of checking whether two processes definable in the syntax of Basic Parallel Processes (BPP) are strongly bisimilar is PSPACE-hard. We also demonstrate that there is a polynomial time reduction from the strong bisimilarity checking problem of regular BPP to the strong regularity (finiteness) checking of BPP. This implies that strong regularity of BPP is also PSPACE-hard.

---

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ů