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

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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ů