2011
Approximating the Termination Value of One-Counter MDPs and Stochastic Games
BRÁZDIL, Tomáš, Václav BROŽEK, Kousha ETESSAMI a Antonín KUČERAZákladní údaje
Originální název
Approximating the Termination Value of One-Counter MDPs and Stochastic Games
Autoři
BRÁZDIL, Tomáš (203 Česká republika, domácí), Václav BROŽEK (203 Česká republika, domácí), Kousha ETESSAMI (840 Spojené státy) a Antonín KUČERA (203 Česká republika, garant, domácí)
Vydání
Berlin, Proceedings of 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), od s. 332-343, 12 s. 2011
Nakladatel
Springer
Další údaje
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í
Kód RIV
RIV/00216224:14330/11:00049981
Organizační jednotka
Fakulta informatiky
ISBN
978-3-642-22011-1
UT WoS
000313861100010
Klíčová slova anglicky
stochastic games; one-counter automata
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 17. 12. 2011 16:19, prof. RNDr. Antonín Kučera, Ph.D.
V originále
We show that all quantitative approximation problems for the termination value for one-counter MDPs and one-counter stochastic games are computable. Specifically, given a one-counter game, and given e > 0, we can compute a value v that approximates the value of the termination game within additive error e, and furthermore we can compute e-optimal strategies for both players in the game.
Česky
V článku je dokázáno, že všechny kvantitativní aproximační problémy v jednočítačových hrách, kde cílem hračů je maximalizovat resp. minimalizovat pravděpodobnost ukončení, jsou algoritmicky řešitelné. Pro zadanou chybu e lze hodnotu hry efektivně aproximovat s přesností e a je také možné vypočítat e-optimální strategie.
Návaznosti
| GAP202/10/1469, projekt VaV |
| ||
| MSM0021622419, záměr |
| ||
| 1M0545, projekt VaV |
|