Qualitative Reachability in Stochastic BPA Games

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

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