Author(s):

Chatterjee, Krishnendu; Doyen, Laurent; Henzinger, Thomas A; Raskin, JeanFrançois

Title: 
Algorithms for omegaregular games with imperfect information

Title Series: 
LNCS

Affiliation 

Abstract: 
We study observationbased strategies for twoplayer turnbased games on graphs with omegaregular objectives. An observationbased 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 fixedpoint algorithm for computing the set of states from which a player can win with a deterministic observationbased strategy for any omegaregular 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 observationbased 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.

Conference Title:

CSL: Computer Science Logic

Volume: 
4207

Conference Dates:

September 2529, 2006

Conference Location:

Szeged, Hungary

ISBN:

3540454586

Publisher:

Springer

Location:

Berlin, Heidelberg

Date Published:

20061113

Start Page: 
287

End Page:

302

Sponsor: 
This research was supported in part by the NSF grants CCR0225610 and CCR0234690, by the SNSF under the IndoSwiss Joint Research Programme, and by the FRFC project “Centre Fédéré en Vérification” funded by the FNRS under grant 2.4530.02.

DOI: 
10.1007/11874683_19

Open access: 
no 