Approximating the Termination Value of One-Counter MDPs and Stochastic Games

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	BRÁZDIL Tomáš BROŽEK Václav ETESSAMI Kousha KUČERA Antonín
Rok publikování	2011
Druh	Článek ve sborníku
Konference	Proceedings of 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Informatika
Klíčová slova	stochastic games; one-counter automata
Popis	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.
Související projekty:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy Formální metody pro analýzu a verifikaci komplexních systémů