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í bisimulační ekvivalence pro systémy s nekonečně mnoha stavy
Autoři	BRÁZDIL Tomáš KUČERA Antonín STRAŽOVSKÝ Oldřich
Rok publikování	2008
Druh	Článek v odborném periodiku
Časopis / Zdroj	Acta informatica
Fakulta / Pracoviště MU	Fakulta informatiky
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:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy