Reachability in Recursive Markov Decision Processes
Název česky | Dosažitelnost pro Markovovy rozhodovací procesy |
---|---|
Autoři | |
Rok publikování | 2006 |
Druh | Článek ve sborníku |
Konference | 17th International Conference on Concurrency Theory |
Fakulta / Pracoviště MU | |
Citace | BRÁZDIL, Tomáš, Václav BROŽEK, Vojtěch FOREJT a Antonín KUČERA. Reachability in Recursive Markov Decision Processes. C. Baier, H. Hermanns (Eds.). In 17th International Conference on Concurrency Theory. Berlin Heidelberg New York: Springer, 2006, s. 358-374. ISBN 3-540-37376-4. |
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: |