Strong Bisimilarity and Regularity of Basic Process Algebra 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 29th International Colloquium on Automata, Languages and Programming (ICALP'02)
Fakulta / Pracoviště MU

Fakulta informatiky

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

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