Informace o publikaci
Deciding probabilistic bisimilarity over infinite-state probabilistic systems
| Název česky | Rozhodnutelnost pravděpodobnostní bisimulační ekvivalence pro systémy s nekonečně mnoha stavy |
|---|---|
| Autoři | |
| Rok publikování | 2008 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Acta informatica |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Informatika |
| Klíčová slova | probabilistic bisimilarity; infinite-state systems |
| Popis | V článku je dokázáno, že pravděpodobnostní bisimulační ekvivalence je algoritmicky rozhodnutelná pro pravěpodobnostní rozšíření BPA a BPP procesů. Pro normované podtřídy těchto procesů dokonce existuje algoritmus s polynomiální časovou složitostí. Dále je dokázáno, že pravěpodobnostní bisimulační ekvivalence je rozhodnutelná v exponenciálním čase i mezi procesy pravděpodobnostních zásobníkových automatů a procesy s konečně mnoha stavy. |
| Související projekty: |