Informace o publikaci
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 | |
| 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: |