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

SRBA, Jiří. Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard. In Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02). Netherlands: Springer-Verlag, 2002, p. 716-727.

Basic information

Original name

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

Authors

SRBA, Jiří (203 Czech Republic, guarantor)

Edition

Netherlands, Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02), p. 716-727, 2002

Publisher

Springer-Verlag

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10000 1. Natural Sciences

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

RIV identification code

RIV/00216224:14330/02:00007147

Organization unit

Faculty of Informatics

Keywords in English

bisimilarity checking; complexity; infinite systems

Tags

bisimilarity checking, complexity, infinite systems

---

Abstract

V originále

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.

---

Links

GA201/00/0400, research and development project	Name: Nekonečně stavové souběžné systémy - modely a verifikace Investor: Czech Science Foundation, Infinite state concurrent systems - models and verification
MSM 143300001, plan (intention)	Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing