Qualitative Reachability in Stochastic BPA Games

• Autoři: BRÁZDIL Tomáš; BROŽEK Václav; KUČERA Antonín; OBDRŽÁLEK Jan
• Rok publikování: 2011
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Information and Computation
• Fakulta / Pracoviště MU: Fakulta informatiky
• Obor: Informatika
• Klíčová slova: pushdown automata; turn-based games
• Popis: V článku je uvažována třída nekonečně-stavových her generovaných zásobníkovými automaty bez stavové jednotky, kde je výherní kritérium specifikováno jako regulární množina cílových konfigurací a omezením tvaru `>0' nebo `=1'. Cílem jednoho hráče je maximalizovat pravděpodobnost dosažení cílové konfigurace tak, aby bylo uvedené omezení splněno, zatímco druhý hráč se snaží o opak. Je dokázáno, problém určení vítěze v takovéto hře je řešitelný v polynomiálním čase pro omezení `>0', resp. v polynomiálním čase pomocí NP int. co-NP orákula pro omezení `=1'. Dále je ukázáno, že výherní region obou hráčů je regulární, a je podán algoritmus pro syntézu výherních strategií obou hráčů.

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ů