Informace o publikaci

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

Druh Článek v odborném periodiku
Časopis / Zdroj BRICS Notes Series
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info