Stochastic Games with Branching-Time Winning Objectives

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Stochastické hry s výherním kritériem určeným formulí větvícího se času
Autoři

BRÁZDIL Tomáš BROŽEK Václav FOREJT Vojtěch KUČERA Antonín

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

Fakulta informatiky

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:

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