| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/12:00057577 |
| Název v původním jazyce | Minimizing Expected Termination Time in One-Counter Markov Decision Processes |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2012 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 1 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | D - Článek ve sborníku |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Výsledek hodnocený již v předchozím hodnocení, body se přebírají |
| Bodové ohodnocení | 44,376 |
| Faktor korekce | 77,6 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 34,420 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Masarykova univerzita / Fakulta informatiky | ano | 85,7 % | 38,036 | 29,503 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 4 |
| Počet domácích tvůrců | 3 |
| Tvůrce | Brázdil Tomáš (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 1762834) |
| Tvůrce | Kučera Antonín (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 9872655) |
| Tvůrce | Novotný Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 2158507) |
| Tvůrce | Wojtczak Dominik (státní příslušnost: PL - Polská republika) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | 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. |
| Klíčová slova | one-counter automata; markov decision processes |
| Název sborníku | Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012) |
| Rozsah stran | 141-152 |
| Forma vydání | P - Tištěná verze „print“ |
| ISSN | 0302-9743 |
| ISBN | 9783642315848 |
| Počet stran výsledku | 12 |
| Název nakladatele | Springer-Verlag |
| Místo vydání | Berlin |
| Místo konání akce | Warwick |
| Rok konání akce | 2012 |
| Typ akce podle státní příslušnoti účastníků | WRD - Světová |
| DOI výsledku | 10.1007/978-3-642-31585-5_16 |
| Údaje o tomto záznamu o výsledku |
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2013 |
| Systémové označení dodávky dat | RIV13-GA0-14330___/02:2 |
| Specifikace | RIV/00216224:14330/12:00057577!RIV13-GA0-14330___ |
| Kontrolní kód | [BB9CD208EA48] |
| Jiný výskyt tohoto výsledku se v RIV nenachází |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | GAP202/10/1469 - Formální metody pro analýzu a verifikaci komplexních systémů (2010-2014, GA0/GA) |
| Projekt | GPP202/12/P612 - Formální verifikace stochastických systémů s reálným časem (2012-2014, GA0/GP) |