The complexity of partial-observation parity games

K. Chatterjee, L. Doyen, in:, C. Fermüller, A. Voronkov (Eds.), Springer, 2010, pp. 1–14.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
Editor
;
Department
Series Title
LNCS
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.
Publishing Year
Date Published
2010-12-09
Volume
6397
Page
1 - 14
Conference
LPAR: Logic for Programming, Artificial Intelligence, and Reasoning
Conference Location
Yogyakarta, Indonesia
Conference Date
2010-10-10 – 2010-10-15
IST-REx-ID

Cite this

Chatterjee K, Doyen L. The complexity of partial-observation parity games. In: Fermüller C, Voronkov A, eds. Vol 6397. Springer; 2010:1-14. doi:10.1007/978-3-642-16242-8_1
Chatterjee, K., & Doyen, L. (2010). The complexity of partial-observation parity games. In C. Fermüller & A. Voronkov (Eds.) (Vol. 6397, pp. 1–14). Presented at the LPAR: Logic for Programming, Artificial Intelligence, and Reasoning, Yogyakarta, Indonesia: Springer. https://doi.org/10.1007/978-3-642-16242-8_1
Chatterjee, Krishnendu, and Laurent Doyen. “The Complexity of Partial-Observation Parity Games.” edited by Christian Fermüller and Andrei Voronkov, 6397:1–14. Springer, 2010. https://doi.org/10.1007/978-3-642-16242-8_1.
K. Chatterjee and L. Doyen, “The complexity of partial-observation parity games,” presented at the LPAR: Logic for Programming, Artificial Intelligence, and Reasoning, Yogyakarta, Indonesia, 2010, vol. 6397, pp. 1–14.
Chatterjee K, Doyen L. 2010. The complexity of partial-observation parity games. LPAR: Logic for Programming, Artificial Intelligence, and Reasoning, LNCS, vol. 6397. 1–14.
Chatterjee, Krishnendu, and Laurent Doyen. The Complexity of Partial-Observation Parity Games. Edited by Christian Fermüller and Andrei Voronkov, vol. 6397, Springer, 2010, pp. 1–14, doi:10.1007/978-3-642-16242-8_1.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar