BRÁZDIL, Tomáš, Václav BROŽEK, Kousha ETESSAMI a Antonín KUČERA. Approximating the Termination Value of One-Counter MDPs and Stochastic Games. In Luca Aceto, Monika Henzinger, Jiří Sgall. Proceedings of 38th International Colloquium on Automata, Languages and Programming (ICALP 2011). Berlin: Springer, 2011. s. 332-343, 12 s. ISBN 978-3-642-22011-1.
Další formáty:   BibTeX LaTeX RIS
Zá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 americké) 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
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 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ěnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 17. 12. 2011 16:19.
Anotace
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.
Anotace č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 VaVNázev: Formální metody pro analýzu a verifikaci komplexních systémů
Investor: Grantová agentura ČR, Standardní projekty
MSM0021622419, záměrNázev: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 14. 10. 2019 22:36