Reachability in Recursive Markov Decision Processes

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Dosažitelnost v rekurzivních Markovových rozhodovacích procesech
Autoři

BRÁZDIL Tomáš BROŽEK Václav FOREJT Vojtěch KUČERA Antonín

Rok publikování 2008
Druh Článek v odborném periodiku
Časopis / Zdroj Information and Computation
Fakulta / Pracoviště MU

Fakulta informatiky

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:

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