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

• 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
• 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ů