Qualitative Reachability in Stochastic BPA Games

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Kvalitativní dosažitelnost ve stochastických BPA hrách
Autoři

BRÁZDIL Tomáš BROŽEK Václav KUČERA Antonín OBDRŽÁLEK Jan

Rok publikování 2009
Druh Článek ve sborníku
Konference Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www DOI
Obor Informatika
Klíčová slova stochastic games; reachability; BPA
Popis Uvažujeme třídu nekonečně stavových her generovaných bezstavovými zásobníkovými automaty (nebo ekvivalentně 1-východovými rekurzivními stavovými automaty), kde výherní podmínka je zadána regulární množinou cílových konfigurací a kvalitativním omezením pravděpodobnosti ">0" nebo "=1". Cílem jednoho hráče je maximalizovat pravděpodobnost dosažení cílové množiny, aby bylo omezení kladené na tuto pravděpodobnost splněno, zatímco cílem druhého hráče je opak. Dokázali jsme, že určování vítěze takové hry patří jak do složitostní třídy NP, tak do coNP. Dále jsme dokázali, že množiny výherních konfigurací jsou regulární pro každého z hráčů, a popsali jsme algritmy pro výpočet příslušných konečných automatů. Závěrem jsme dokázali že výherní strategie mohou být efektivně zadány.
Související projekty:

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