Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Rozhodnutelnost pravděpodobnostní bisimulace pro nekonečně-stavové pravděpodobnostní systémy
Autoři	BRÁZDIL Tomáš KUČERA Antonín STRAŽOVSKÝ Oldřich
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	Fakulta informatiky
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:	Verifikace nekonečně stavových systémů Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů