Informace o publikaci

One-Counter Markov Decision Processes

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: