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

• 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
• 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ů