Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard
| Authors | |
|---|---|
| Year of publication | 2002 |
| Type | Article in Proceedings |
| Conference | Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02) |
| MU Faculty or unit | |
| Citation | |
| Field | Information theory |
| Keywords | bisimilarity checking; complexity; infinite systems |
| Description | 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. |
| Related projects: |