Refining Undecidability Border of Weak Bisimilarity.
| Název česky | Zjemneni hranice nerozhodnutelnosti pro slabou bisimulaci |
|---|---|
| Autoři | |
| Rok publikování | 2005 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | BRICS Notes Series |
| Fakulta / Pracoviště MU | |
| 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: |