Algorithms for omega-regular games with imperfect information

Chatterjee K, Doyen L, Henzinger TA, Raskin J. 2006. Algorithms for omega-regular games with imperfect information. CSL: Computer Science Logic, LNCS, vol. 4207, 287–302.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
Chatterjee, KrishnenduISTA ; Doyen, Laurent; Henzinger, Thomas AISTA ; Raskin, Jean-François
Series Title
LNCS
Abstract
We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buchi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.
Publishing Year
Date Published
2006-11-13
Publisher
Springer
Acknowledgement
This research was supported in part by the NSF grants CCR-0225610 and CCR-0234690, by the SNSF under the Indo-Swiss Joint Research Programme, and by the FRFC project “Centre Fédéré en Vérification” funded by the FNRS under grant 2.4530.02.
Volume
4207
Page
287 - 302
Conference
CSL: Computer Science Logic
IST-REx-ID

Cite this

Chatterjee K, Doyen L, Henzinger TA, Raskin J. Algorithms for omega-regular games with imperfect information. In: Vol 4207. Springer; 2006:287-302. doi:10.1007/11874683_19
Chatterjee, K., Doyen, L., Henzinger, T. A., & Raskin, J. (2006). Algorithms for omega-regular games with imperfect information (Vol. 4207, pp. 287–302). Presented at the CSL: Computer Science Logic, Springer. https://doi.org/10.1007/11874683_19
Chatterjee, Krishnendu, Laurent Doyen, Thomas A Henzinger, and Jean Raskin. “Algorithms for Omega-Regular Games with Imperfect Information,” 4207:287–302. Springer, 2006. https://doi.org/10.1007/11874683_19.
K. Chatterjee, L. Doyen, T. A. Henzinger, and J. Raskin, “Algorithms for omega-regular games with imperfect information,” presented at the CSL: Computer Science Logic, 2006, vol. 4207, pp. 287–302.
Chatterjee K, Doyen L, Henzinger TA, Raskin J. 2006. Algorithms for omega-regular games with imperfect information. CSL: Computer Science Logic, LNCS, vol. 4207, 287–302.
Chatterjee, Krishnendu, et al. Algorithms for Omega-Regular Games with Imperfect Information. Vol. 4207, Springer, 2006, pp. 287–302, doi:10.1007/11874683_19.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar