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

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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:	Nekonečně stavové souběžné systémy - modely a verifikace Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů