| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/13:00065955 |
| Název v původním jazyce | Approximating the termination value of one-counter MDPs and stochastic games |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2013 |
| 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 | 2 |
| Ú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í | Jimp - Článek v impaktovaném časopise evidovaném ve Web of Science |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Článek v impaktovaném časopise evidovaném ve Web of Science |
| Bodové ohodnocení | 17,576 |
| Faktor korekce | 86,1 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 15,137 |
| 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 % | 15,065 | 12,974 |
|
| 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 | Brožek Václav (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 5532787) |
| Tvůrce | Etessami Kousha (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska) |
| Tvůrce | Kučera Antonín (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 9872655) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | One-counter MDPs (OC-MDPs) and one-counter simple stochastic games (OC-SSGs) are 1-player, and 2-player turn-based zero-sum, stochastic games played on the transition graph of classic one-counter automata (equivalently, pushdown automata with a 1-letter stack alphabet). A key objective for the analysis and verification of these games is the termination objective, where the players aim to maximize (minimize, respectively) the probability of hitting counter value 0, starting at a given control state and given counter value. Recently, we studied qualitative decision problems ("is the optimal termination value equal to 1?") for OC-MDPs (and OC-SSGs) and showed them to be decidable in polynomial time (in NP intersection coNP, respectively). However, quantitative decision and approximation problems ("is the optimal termination value at least p", or "approximate the termination value within epsilon") are far more challenging. |
| Klíčová slova | Markov decision processes; one-counter automata |
| Kód UT ISI | 000313861100010 |
| Název periodka | Information and Computation |
| Rozsah stran | 121-138 |
| ISSN | 0890-5401 |
| Svazek periodika | 222 |
| Číslo periodika v rámci uvedeného svazku | January |
| Stát vydavatele periodika | NL - Nizozemsko |
| Počet stran výsledku | 18 |
| DOI výsledku | 10.1016/j.ic.2012.01.008 |
| Ú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 | 2014 |
| Systémové označení dodávky dat | RIV14-GA0-14330___/01:1 |
| Specifikace | RIV/00216224:14330/13:00065955!RIV14-GA0-14330___ |
| Kontrolní kód | [11D32EDCAD30] |
| Další výskyty tohoto výsledku od stejného předkladatele |
| Dodáno MŠMT v roce 2014 | Záznam s identifikačním kódem RIV/00216224:14330/13:00065955 v dodávce dat RIV14-MSM-14330___/01:1 |
| 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 | 1M0545 - Institut Teoretické Informatiky (2005-2011, MSM/1M) |
| I - Instit. podpora na rozvoj výzkumné organizace |