BRÁZDIL, Tomáš, Antonín KUČERA, Petr NOVOTNÝ and Dominik WOJTCZAK. Minimizing Expected Termination Time in One-Counter Markov Decision Processes. In Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012). Berlin: Springer, 2012. p. 141-152. ISBN 978-3-642-31584-8. doi:10.1007/978-3-642-31585-5_16.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Minimizing Expected Termination Time in One-Counter Markov Decision Processes
Authors BRÁZDIL, Tomáš (203 Czech Republic, belonging to the institution), Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution), Petr NOVOTNÝ (203 Czech Republic, belonging to the institution) and Dominik WOJTCZAK (616 Poland).
Edition Berlin, Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), p. 141-152, 12 pp. 2012.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/12:00057577
Organization unit Faculty of Informatics
ISBN 978-3-642-31584-8
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-642-31585-5_16
UT WoS 000342761300016
Keywords in English one-counter automata; markov decision processes
Tags best3, formela-conference
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 23. 4. 2013 13:16.
Abstract
We consider the problem of computing the value and an optimal strategy for minimizing the expected termination time in one-counter Markov decision processes. Since the value may be irrational and an optimal strategy may be rather complicated, we concentrate on the problems of approximating the value up to a given error epsilon > 0 and computing a finite representation of an epsilon-optimal strategy. We show that these problems are solvable in exponential time for a given configuration, and we also show that they are computationally hard in the sense that a polynomial-time approximation algorithm cannot exist unless P=NP.
Abstract (in Czech)
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.
Links
GAP202/10/1469, research and development projectName: Formální metody pro analýzu a verifikaci komplexních systémů
Investor: Czech Science Foundation, Standard Projects
GPP202/12/P612, research and development projectName: Formální verifikace stochastických systémů s reálným časem (Acronym: Formální verifikace stochastických systémů s reáln)
Investor: Czech Science Foundation, Postdoctoral projects
MUNI/A/0914/2009, internal MU codeName: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV)
Investor: Masaryk University, Grant Agency of Masaryk University, Category A
PrintDisplayed: 21. 10. 2021 10:20