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

SRBA, Jiří. Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard. In Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02). Holland: Springer-Verlag, 2002, p. 535-546.

Basic information

• Original name: Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard
• Authors: SRBA, Jiří (203 Czech Republic, guarantor).
• Edition: Holland, Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02), p. 535-546, 2002.
• Publisher: Springer-Verlag

Other information

• Original 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:00005680
• Organization unit: Faculty of Informatics
• Keywords in English: bisimilarity checking; complexity; infinite systems
• Tags: bisimilarity checking, complexity, infinite systems

Abstract

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.

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