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í

Označené pro přenos do RIV

Ano

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ů