Informace o publikaci
Qualitative Reachability in Stochastic BPA Games
| Název česky | Kvalitativní dosažitelnost ve stochastických BPA hrách |
|---|---|
| Autoři | |
| 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 | |
| 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: |