Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard
| Autoři | |
|---|---|
| Rok publikování | 2002 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Teorie informace |
| Klíčová slova | bisimilarity checking; complexity; infinite systems |
| Popis | 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. |
| Související projekty: |