Informace o publikaci
Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems
| Název česky | Rozhodnutelnost pravděpodobnostní bisimulace pro nekonečně-stavové pravděpodobnostní systémy |
|---|---|
| Autoři | |
| Rok publikování | 2004 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of 15th International Conference on Concurrency Theory (CONCUR 2004) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Informatika |
| Klíčová slova | probabilistic bisimilarity; probabilistic systems |
| Popis | V článku je dokázáno, že pravděpodobnostní bisimulace je rozhodnutelná pro pravděpodobnostní rozšíření BPA a BPP procesů. Pro normované podtřídy pravděpodobnostních BPA a BPP procesů jsou prezentovány algoritmy, jejichž časová složitost je polynomiální. Dále je dokázáno, že pravděpodobnostní bisimulace mezi pravděpodobnostními zásobníkovými automaty a konečně-stavovými pravděpodobnostními systémy je rozhodnutelná v exponenciálním čase. Pokud je počet kontrolních stavů zásobníkového automatu omezen fixní konstantou, pak je tato časová složitost polynomiální. |
| Související projekty: |