Reachability in Recursive Markov Decision Processes

Varování

Publikace nespadá pod Pedagogickou fakultu, 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.