Informace o publikaci
Stochastic Games with Branching-Time Winning Objectives
| Název česky | Stochastické hry s výherním kritériem určeným formulí větvícího se času |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek ve sborníku |
| Konference | 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, Washington, USA, Proceedings |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Informatika |
| Klíčová slova | Stochastic games; branching-time temporal logics |
| Popis | V článku se zkoumají vlastnosti třídy stochastických her, kde je výherní kritérium určeno danou formulí temporální logiky PCTL. Tyto hry obecně nejsou determinované a výherní strategie mohou vyžadovat paměť a/nebo náhodnostní tahy. Hlavní prezentované výsledky se týkají strategií závisejících na historii hry. Zejména je dokázáno, že problém existence výherní strategie závislé na historii je vysoce nerozhodnutelný pro hry s 1.5 hráči, kde výherním kritériem je formule fragmentu L(F^{=5/8},F^{=1},F^{>0},G^{=1}) logiky PCTL. Rovněž je dokázáno, že tento problém je rozhodnutelný (a EXPTIME-úplný) pro fragment L(F{=1},F^{>0},G^{=1}), kde výherní strategie vyžadují pouze konečnou paměť. |
| Související projekty: |