Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A. and Raskin, <br> Jean-Francois - Algorithms for Omega-Regular Games with Imperfect Information

lmcs:1094 - Logical Methods in Computer Science, July 27, 2007, Volume 3, Issue 3
Algorithms for Omega-Regular Games with Imperfect Information

Authors: Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A. and Raskin, <br> Jean-Francois

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 Buechi 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.


Source : oai:arXiv.org:0706.2619
DOI : 10.2168/LMCS-3(3:4)2007
Volume: Volume 3, Issue 3
Published on: July 27, 2007
Submitted on: January 3, 2007
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computer Science and Game Theory,F.4.1


Share

Consultation statistics

This page has been seen 101 times.
This article's PDF has been downloaded 61 times.