Refining Undecidability Border of Weak Bisimilarity. (full version of INFINITY 2005 paper)

• Název česky: Zjemneni hranice nerozhodnutelnosti pro slabou bisimulaci
• Autoři: KŘETÍNSKÝ Mojmír; ŘEHÁK Vojtěch; STREJČEK Jan
• Rok publikování: 2005
• Druh: Prezentace v oblasti VaV (AV tvorba, WEB aplikace apod.)
• Fakulta / Pracoviště MU: Fakulta informatiky
• Popis: Slaba bisimulace je jednou z nejvice studovanych behavioralnich ekvivalenci. Tato ekvivalence je nerozhodnutelna pro pushdown processes (PDA), process algebras (PA), a multiset automata (MSA, zname tez jako parallel pushdown processes, PPDA). Jeji rozhodnutelnost je otevrenym problemem pro question basic process algebras} (BPA) a basic parallel processes (BPP). Ukazujeme, ze hranici jeji nerozhodnutelnosti lze posunout ke zminenym tridam BPA a BPP, a to tak, tato ekvivalence zustava nerohodnutelnou i pro slabe rozsirene verze BPA a BPP.

Související projekty

• Verifikace nekonečně stavových systémů
• Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů
• Techniky automatické verifikace a validace softwarových a hardwarových systémů
• Institut Teoretické Informatiky
• Vysoce paralelní a distribuované výpočetní systémy