Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Strategy construction for parity games with imperfect information
 
research article

Strategy construction for parity games with imperfect information

Berwanger, Dietmar
•
Chatterjee, Krishnendu
•
De Wulf, Martin
Show more
2010
Information And Computation

We consider two-player parity games with imperfect information in which strategies rely on observations that provide imperfect information about the history of a play. To solve such games, i.e., to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-information game. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.ic.2009.09.006
Web of Science ID

WOS:000281830300007

Author(s)
Berwanger, Dietmar
Chatterjee, Krishnendu
De Wulf, Martin
Doyen, Laurent
Henzinger, Thomas A.  
Date Issued

2010

Published in
Information And Computation
Volume

208

Start page

1206

End page

1220

Subjects

Infinite Games

•

Universality

•

Automata

•

Graphs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MTC  
Available on Infoscience
December 16, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/75204
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés