Refining Undecidability Border of Weak Bisimilarity.

• 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: Článek v odborném periodiku
• Časopis / Zdroj: BRICS Notes Series
• Fakulta / Pracoviště MU: Fakulta informatiky
• www: http://www.brics.dk/NS/05/4/
• Obor: Informatika
• Klíčová slova: process rewrite systems; state extension; infinite-state; (un)decidability; weak bisimulation
• Popis: Slaba bisimulace je jednou z nejvice studovanych behavioralnich ekvivalenci. Tato ekvivalence je nerozhodnutelna pro zasobnikove procesy (PDA), procesove algebry (PA), and multimnozinove automaty (MSA, zname tez jako paralelni zasobnikove procesy, PPDA). Jeji rozhodnutelnost je otevrenym problemem pro zakladni procesove algebry (BPA) a zakladni paralelni procesy (BPP). Ukazujeme, ze hranici jeji nerozhodnutelnosti lze posunout ke zminenym tridam BPA a BPP. Konkretne ukazeme, ze tato ekvivalence zustava nerohodnutelnou i pro slabe rozsirene verze BPA a BPP.

Související projekty

• Verifikace nekonečně stavový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