Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	KUČERA Antonín MAYR Richard
Rok publikování	2002
Druh	Článek v odborném periodiku
Časopis / Zdroj	Theoretical Computer Science
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Počítačový hardware a software
Klíčová slova	concurrency; infinite-state systems; bisimilarity
Popis	We prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes (BPA) and normed Basic Parallel Processes (normed BPP). To the best of our knowledge, these are the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.
Související projekty:	Nekonečně stavové souběžné systémy - modely a verifikace Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů