Qualitative Reachability in Stochastic BPA Games

Logo poskytovatele

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 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.