BRÁZDIL, Tomáš, Antonín KUČERA, Petr NOVOTNÝ a 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. s. 141-152. ISBN 978-3-642-31584-8. doi:10.1007/978-3-642-31585-5_16.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Minimizing Expected Termination Time in One-Counter Markov Decision Processes
Autoři BRÁZDIL, Tomáš (203 Česká republika, domácí), Antonín KUČERA (203 Česká republika, garant, domácí), Petr NOVOTNÝ (203 Česká republika, domácí) a Dominik WOJTCZAK (616 Polsko).
Vydání Berlin, Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), od s. 141-152, 12 s. 2012.
Nakladatel Springer
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Forma vydání tištěná verze "print"
Impakt faktor Impact factor: 0.402 v roce 2005
Kód RIV RIV/00216224:14330/12:00057577
Organizační jednotka Fakulta informatiky
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
Klíčová slova anglicky one-counter automata; markov decision processes
Štítky best3, formela-conference
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 23. 4. 2013 13:16.
Anotace
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.
Anotace česky
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.
Návaznosti
GAP202/10/1469, projekt VaVNázev: Formální metody pro analýzu a verifikaci komplexních systémů
Investor: Grantová agentura ČR, Standardní projekty
GPP202/12/P612, projekt VaVNázev: Formální verifikace stochastických systémů s reálným časem (Akronym: Formální verifikace stochastických systémů s reáln)
Investor: Grantová agentura ČR, Postdoktorské projekty
MUNI/A/0914/2009, interní kód MUNázev: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV)
Investor: Masarykova univerzita, Grantová agentura MU, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
VytisknoutZobrazeno: 21. 10. 2021 11:01