Informace o publikaci
Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard
| Autoři | |
|---|---|
| Rok publikování | 2002 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Teorie informace |
| Klíčová slova | bisimilarity checking; complexity; infinite systems |
| Popis | 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. |
| Související projekty: |