Algorithms for Omega-Regular Games with Imperfect Information

Details Algorithms for Omega-Regular Games with Imperfect Information Algorithms for Omega-Regular Games with Imperfect Information

2007-06-18

arxiv.org/abs/0706.2619v3

LMCS 3 (3:4) 2007

Computer Science

Logic in Computer Science

24 pages. A preliminary version of this paper appeared in the Proceedings of the International Conference for Computer Science

Scientific paper

10.2168/LMCS-3(3:4)2007

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.

Affiliated with

Also associated with

No associations

Rating

Algorithms for Omega-Regular Games with Imperfect Information does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for Omega-Regular Games with Imperfect Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Omega-Regular Games with Imperfect Information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-609915