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

Proceedings paper

Field of Study

10000 1. Natural Sciences

Country of publisher

Netherlands

Confidentiality degree

is not subject to a state or trade secret

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