---
_id: '2947'
abstract:
- lang: eng
text: 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.
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.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
citation:
ama: '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'
apa: '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'
chicago: 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.
ieee: '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.'
ista: '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.'
mla: 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.
short: K. Chatterjee, M. Chmelik, R. Majumdar, in:, Springer, 2012, pp. 385–399.
conference:
end_date: 2012-10-06
location: Thiruvananthapuram, India
name: ' ATVA: Automated Technology for Verification and Analysis'
start_date: 2012-10-03
date_created: 2018-12-11T12:00:29Z
date_published: 2012-06-01T00:00:00Z
date_updated: 2021-01-12T07:39:58Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-33386-6_30
ec_funded: 1
intvolume: ' 7561'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1202.4140
month: '06'
oa: 1
oa_version: Preprint
page: 385 - 399
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Springer
publist_id: '3785'
quality_controlled: '1'
scopus_import: 1
status: public
title: Equivalence of games with probabilistic uncertainty and partial observation
games
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7561
year: '2012'
...