Minimizing Expected Termination Time in One-Counter Markov Decision Processes

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	BRÁZDIL Tomáš KUČERA Antonín NOVOTNÝ Petr WOJTCZAK Dominik
Rok publikování	2012
Druh	Článek ve sborníku
Konference	Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Doi	https://doi.org/10.1007/978-3-642-31585-5_16
Obor	Informatika
Klíčová slova	one-counter automata; markov decision processes
Přiložené soubory	1205.1473v1.pdf
Popis	V článku se zabýváme problémem minimalizace času ukončení výpočtu v Markovových rozhodovacích procesech s jedním čítačem. Prezentujeme algoritmus s exponenciální časovou složitostí, který pro libovolné zadané e>0 aproximuje (s přesností e) optimální hodnotu času ukončení v zadané počáteční konfiguraci, a zároveň vypočítá příslušnou e-optimální strategii. Rovněž ukazujeme, že za předpokladu nerovnosti tříd P a NP nemůže pro tyto problémy existovat polynomiální algoritmus.
Související projekty:	Formální metody pro analýzu a verifikaci komplexních systémů Rozsáhlé výpočetní systémy: modely, aplikace a verifikace Formální verifikace stochastických systémů s reálným časem