![Jak na přijímačky](https://cdn.muni.cz/media/3633702/image_1.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
Informace o publikaci
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: |