Equivalence of games with probabilistic uncertainty and partial observation games

K. Chatterjee, M. Chmelik, R. Majumdar, in:, Springer, 2012, pp. 385–399.


Conference Paper | Published | English
Department
Series Title
LNCS
Abstract
We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems.
Publishing Year
Date Published
2012-06-01
Acknowledgement
The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.
Volume
7561
Page
385 - 399
Conference
ATVA: Automated Technology for Verification and Analysis
Conference Location
Thiruvananthapuram, India
Conference Date
2012-10-03 – 2012-10-06
IST-REx-ID

Cite this

Chatterjee K, Chmelik M, Majumdar R. Equivalence of games with probabilistic uncertainty and partial observation games. In: Vol 7561. Springer; 2012:385-399. doi:10.1007/978-3-642-33386-6_30
Chatterjee, K., Chmelik, M., & Majumdar, R. (2012). Equivalence of games with probabilistic uncertainty and partial observation games (Vol. 7561, pp. 385–399). Presented at the ATVA: Automated Technology for Verification and Analysis, Thiruvananthapuram, India: Springer. https://doi.org/10.1007/978-3-642-33386-6_30
Chatterjee, Krishnendu, Martin Chmelik, and Ritankar Majumdar. “Equivalence of Games with Probabilistic Uncertainty and Partial Observation Games,” 7561:385–99. Springer, 2012. https://doi.org/10.1007/978-3-642-33386-6_30.
K. Chatterjee, M. Chmelik, and R. Majumdar, “Equivalence of games with probabilistic uncertainty and partial observation games,” presented at the ATVA: Automated Technology for Verification and Analysis, Thiruvananthapuram, India, 2012, vol. 7561, pp. 385–399.
Chatterjee K, Chmelik M, Majumdar R. 2012. Equivalence of games with probabilistic uncertainty and partial observation games. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 7561. 385–399.
Chatterjee, Krishnendu, et al. Equivalence of Games with Probabilistic Uncertainty and Partial Observation Games. Vol. 7561, Springer, 2012, pp. 385–99, doi:10.1007/978-3-642-33386-6_30.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar