Other formats:
BibTeX
LaTeX
RIS
@inproceedings{694339, author = {Brázdil, Tomáš and Brožek, Václav and Forejt, Vojtěch and Kučera, Antonín}, address = {Los Alamitos, California}, booktitle = {21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, Washington, USA, Proceedings}, keywords = {Stochastic games; branching-time temporal logics}, language = {eng}, location = {Los Alamitos, California}, isbn = {0-7695-2631-4}, pages = {349-358}, publisher = {IEEE Computer Society}, title = {Stochastic Games with Branching-Time Winning Objectives}, year = {2006} }
TY - JOUR ID - 694339 AU - Brázdil, Tomáš - Brožek, Václav - Forejt, Vojtěch - Kučera, Antonín PY - 2006 TI - Stochastic Games with Branching-Time Winning Objectives PB - IEEE Computer Society CY - Los Alamitos, California SN - 0769526314 KW - Stochastic games KW - branching-time temporal logics N2 - We consider stochastic turn-based games where the winning objectives are given by formulae of the branching-time logic PCTL. These games are generally not determined and winning strategies may require memory and/or randomization. Our main results concern history-dependent strategies. In particular, we show that the problem whether there exists a history-dependent winning strategy in 1.5-player games is highly undecidable, even for objectives formulated in the L(F^{=5/8},F^{=1},F^{>0},G^{=1}) fragment of PCTL. On the other hand, we show that the problem becomes decidable (and in fact EXPTIME-complete) for the L(F{=1},F^{>0},G^{=1}) fragment of PCTL, where winning strategies require only finite memory. This result is tight in the sense that winning strategies for L(F^{=1},F^{>0},G^{=1},G^{>0}) objectives may already require infinite memory. ER -
BRÁZDIL, Tomáš, Václav BROŽEK, Vojtěch FOREJT and Antonín KUČERA. Stochastic Games with Branching-Time Winning Objectives. In \textit{21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, Washington, USA, Proceedings}. Los Alamitos, California: IEEE Computer Society, 2006, p.~349-358. ISBN~0-7695-2631-4.
|