## Semiperfect-Information Games

*Krishnendu Chatterjee and
Thomas A. Henzinger*

Much recent research has focused on the applications of games with
omega-regular objectives in the control and verification of reactive
systems. However, many of the game-based models are ill-suited for
these applications, because they assume that each player has complete
information about the state of the system (they are
"perfect-information" games). This is because in many situations, a
controller does not see the private state of the plant. Such
scenarios are naturally modeled by "partial-information" games. On
the other hand, these games are intractable; for example,
partial-information games with simple reachability objectives are
2EXPTIME-complete.

We study the intermediate case of "semiperfect-information" games,
where one player has complete knowledge of the state, while the other
player has only partial knowledge. This model is appropriate in
control situations where a controller must cope with plant behavior
that is as adversarial as possible, i.e., the controller has partial
information while the plant has perfect information. As is customary,
we assume that the controller and plant take turns to make moves. We
show that these *semiperfect-information turn-based games* are
equivalent to *perfect-information concurrent games*, where the
two players choose their moves simultaneously and independently.
Since the perfect-information concurrent games are well-understood, we
obtain several results of how semiperfect-information turn-based games
differ from perfect-information turn-based games on one hand, and from
partial-information turn-based games on the other hand. In
particular, semiperfect-information turn-based games can benefit from
randomized strategies while the perfect-information variety cannot,
and semiperfect-information turn-based games are in NP ∩ coNP for
all parity objectives.

*Proceedings of the
26th International Conference on Foundations of Software Technology and
Theoretical Computer Science*
(FSTTCS),
Lecture Notes in Computer Science 3821,
Springer, 2005, pp. 1-18.

Download inofficial, sometimes updated
PostScript /
PDF document.
© 2005 Springer.