| Identifikační kód | RIV/00216224:14330/13:00065955 |
|---|
| Název v anglické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 - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2013 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 3 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Tomáš Brázdil (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 1762834)
Václav Brožek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 5532787)
Kousha Etessami (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska)
Antonín Kučera (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 9872655) |
|---|
| Popis výsledku v anglické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-letterstack 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 oddělená středníkem | Markov decision processes; one-counter automata |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1016/j.ic.2012.01.008 |
|---|