One-Counter Markov Decision Processes

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

BRÁZDIL Tomáš BROŽEK Václav ETESSAMI Kousha KUČERA Antonín WOJTCZAK Dominik

Rok publikování 2010
Druh Článek ve sborníku
Konference Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www Link to SODA 2010 electronic proceedings
Obor Informatika
Klíčová slova Markov decision proces; probability; one counter MDP; reachability; termination
Popis V článku jsou studovány Markovovy rozhodovací procesy generované procesy s jedním neomezeným čítačem. Uvažovaná výherní kritéria zahrnují dosažitelnost a různé limitní vlastnosti běhů. V článku je dokázáno, že některé varianty těchto problémů jsou efektivně řešitelné v polynomiálním čase. O jiných je ukázáno, že jsou PSPACE těžké a je podán algoritmus s exponenciální časovou složitostí.
Související projekty:

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

Další info