Reachability in Recursive Markov Decision Processes

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	Dosažitelnost pro Markovovy rozhodovací procesy
Autoři	BRÁZDIL Tomáš BROŽEK Václav FOREJT Vojtěch KUČERA Antonín
Rok publikování	2006
Druh	Článek ve sborníku
Konference	17th International Conference on Concurrency Theory
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Informatika
Klíčová slova	Markov decision processes; reachability
Popis	V článku se zkoumají vlastnosti nekonečně-stavových Markovových rozhodovacích procesů, které jsou generované zásobníkovými procesy bez kontrolních stavů. Tato třída procesů odpovídá hrám s 1.5 hráči nad grafy, které jsou generované BPA systémy. Dokážeme, že kvalitativní problém dosažitelnosti je pro tuto třídu procesů rozhodnutelný v polynomiálním čase. Aplikaci tohoto výsledku prokážeme EXPTIME-úplnost problému platnosti dané kvalitativní PCTL formule v daném stavu daného procesu.
Související projekty:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy