One-Counter Markov Decision Processes

Varování

Publikace nespadá pod Filozofickou fakultu, 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:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy