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:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy