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

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

SRBA Jiří

Rok publikování 2002
Druh Článek ve sborníku
Konference Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02)
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Obor Teorie informace
Klíčová slova bisimilarity checking; complexity; infinite systems
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.