---
OA_type: closed access
_id: '4541'
abstract:
- lang: eng
  text: "Much recent research has focused on the applications of games with ω-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.\r\nWe 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.\r\n"
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: 'Chatterjee K, Henzinger TA. Semiperfect-information games. In: <i>Proceedings
    of the 25th International Conference on Foundations of Software Technology and
    Theoretical Computer Science</i>. Vol 3821. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2005:1-18. doi:<a href="https://doi.org/10.1007/11590156_1">10.1007/11590156_1</a>'
  apa: 'Chatterjee, K., &#38; Henzinger, T. A. (2005). Semiperfect-information games.
    In <i>Proceedings of the 25th international conference on Foundations of Software
    Technology and Theoretical Computer Science</i> (Vol. 3821, pp. 1–18). Hyderabad,
    India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.1007/11590156_1">https://doi.org/10.1007/11590156_1</a>'
  chicago: Chatterjee, Krishnendu, and Thomas A Henzinger. “Semiperfect-Information
    Games.” In <i>Proceedings of the 25th International Conference on Foundations
    of Software Technology and Theoretical Computer Science</i>, 3821:1–18. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2005. <a href="https://doi.org/10.1007/11590156_1">https://doi.org/10.1007/11590156_1</a>.
  ieee: K. Chatterjee and T. A. Henzinger, “Semiperfect-information games,” in <i>Proceedings
    of the 25th international conference on Foundations of Software Technology and
    Theoretical Computer Science</i>, Hyderabad, India, 2005, vol. 3821, pp. 1–18.
  ista: 'Chatterjee K, Henzinger TA. 2005. Semiperfect-information games. Proceedings
    of the 25th international conference on Foundations of Software Technology and
    Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical
    Computer Science, LNCS, vol. 3821, 1–18.'
  mla: Chatterjee, Krishnendu, and Thomas A. Henzinger. “Semiperfect-Information Games.”
    <i>Proceedings of the 25th International Conference on Foundations of Software
    Technology and Theoretical Computer Science</i>, vol. 3821, Schloss Dagstuhl -
    Leibniz-Zentrum für Informatik, 2005, pp. 1–18, doi:<a href="https://doi.org/10.1007/11590156_1">10.1007/11590156_1</a>.
  short: K. Chatterjee, T.A. Henzinger, in:, Proceedings of the 25th International
    Conference on Foundations of Software Technology and Theoretical Computer Science,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2005, pp. 1–18.
conference:
  end_date: 2005-12-18
  location: Hyderabad, India
  name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
  start_date: 2005-12-15
date_created: 2018-12-11T12:09:23Z
date_published: 2005-12-07T00:00:00Z
date_updated: 2026-10-23T08:41:18Z
day: '07'
doi: 10.1007/11590156_1
extern: '1'
fulldoi: https://doi.org/10.1007/11590156_1
intvolume: '      3821'
language:
- iso: eng
month: '12'
oa_version: None
page: 1 - 18
publication: Proceedings of the 25th international conference on Foundations of Software
  Technology and Theoretical Computer Science
publication_identifier:
  isbn:
  - '9783540304951'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '182'
status: public
title: Semiperfect-information games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3821
year: '2005'
...