@inproceedings{3858,
abstract = {We consider two-player zero-sum games on graphs. On the basis of the information available to the players these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have com- plete view of the game). We survey the complexity results for the problem of de- ciding the winner in various classes of partial-observation games with ω-regular winning conditions specified as parity objectives. We present a reduction from the class of parity objectives that depend on sequence of states of the game to the sub-class of parity objectives that only depend on the sequence of observations. We also establish that partial-observation acyclic games are PSPACE-complete.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
editor = {Fermüller, Christian and Voronkov, Andrei},
location = {Yogyakarta, Indonesia},
pages = {1 -- 14},
publisher = {Springer},
title = {{The complexity of partial-observation parity games}},
doi = {10.1007/978-3-642-16242-8_1},
volume = {6397},
year = {2010},
}