Reachability in Recursive Markov Decision Processes
| Název česky | Dosažitelnost v rekurzivních Markovových rozhodovacích procesech |
|---|---|
| Autoři | |
| Rok publikování | 2008 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Information and Computation |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Informatika |
| Klíčová slova | Markov decision processes; temporal logics; reachability |
| Popis | V článku se zkoumá třída nekonečně-stavových Markovových rozhodovacích procesů generovaná zásobníkovými automaty bez stavové jednotky. Tato třída odpovídá hrám s 1.5 hráči nad grafy generovanými BPA systémy nebo (ekvivalentně) rekuzivními stavovými automaty s jedním exitem. Rozšířený problém dosažitelnosti je dán dvěma množinami S a T bezpečných a koncových stavů, kde příslušnost do S a T závisí pouza na symbolu na vrcholu zásobníku. V článku se zkoumá algortimická rozhodnutelnost a složitost otázky existence vhodné strategie, která zajistí, že pravděpodobnost dosažení koncového stavu přes bezpečné stavy je rovna danému x z množiny {0,1}. Je ukázáno, že tato otázka je algoritmicky rozhodnutelná v polynomiálním čase, a že množina všech konfigurací, pro které vhodná strategie existuje, je efektivně regulární. |
| Související projekty: |