SRBA, Jiří. Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard. In Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02). Netherlands: Springer-Verlag, 2002, s. 716-727.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard
Autoři SRBA, Jiří (203 Česká republika, garant).
Vydání Netherlands, Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02), s. 716-727, 2002.
Nakladatel Springer-Verlag
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10000 1. Natural Sciences
Stát vydavatele Nizozemské království
Utajení není předmětem státního či obchodního tajemství
Kód RIV RIV/00216224:14330/02:00007147
Organizační jednotka Fakulta informatiky
Klíčová slova anglicky bisimilarity checking; complexity; infinite systems
Štítky bisimilarity checking, complexity, infinite systems
Změnil Změnil: Prof. Jiří Srba, Ph.D., učo 2841. Změněno: 21. 5. 2003 09:46.
Anotace
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.
Návaznosti
GA201/00/0400, projekt VaVNázev: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Nekonečně stavové souběžné systémy - modely a verifikace
MSM 143300001, záměrNázev: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů
VytisknoutZobrazeno: 26. 4. 2024 10:50