---
_id: '2213'
abstract:
- lang: eng
text: We consider two-player partial-observation stochastic games on finitestate
graphs where player 1 has partial observation and player 2 has perfect observation.
The winning condition we study are ε-regular conditions specified as parity objectives.
The qualitative-analysis problem given a partial-observation stochastic game and
a parity objective asks whether there is a strategy to ensure that the objective
is satisfied with probability 1 (resp. positive probability). These qualitative-analysis
problems are known to be undecidable. However in many applications the relevant
question is the existence of finite-memory strategies, and the qualitative-analysis
problems under finite-memory strategies was recently shown to be decidable in
2EXPTIME.We improve the complexity and show that the qualitative-analysis problems
for partial-observation stochastic parity games under finite-memory strategies
are EXPTIME-complete; and also establish optimal (exponential) memory bounds for
finite-memory strategies required for qualitative analysis.
acknowledgement: 'This research was supported by European project Cassting (FP7-601148),
NSF grants CNS 1049862 and CCF-1139011, by NSF Expe ditions in Computing project
“ExCAPE: Expeditions in Computer Augmented Program Engineering”, by BSF grant 9800096,
and by gift from Intel.'
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Sumit
full_name: Nain, Sumit
last_name: Nain
- first_name: Moshe
full_name: Vardi, Moshe
last_name: Vardi
citation:
ama: 'Chatterjee K, Doyen L, Nain S, Vardi M. The complexity of partial-observation
stochastic parity games with finite-memory strategies. In: Vol 8412. Springer;
2014:242-257. doi:10.1007/978-3-642-54830-7_16'
apa: 'Chatterjee, K., Doyen, L., Nain, S., & Vardi, M. (2014). The complexity
of partial-observation stochastic parity games with finite-memory strategies (Vol.
8412, pp. 242–257). Presented at the FoSSaCS: Foundations of Software Science
and Computation Structures, Grenoble, France: Springer. https://doi.org/10.1007/978-3-642-54830-7_16'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. “The
Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies,”
8412:242–57. Springer, 2014. https://doi.org/10.1007/978-3-642-54830-7_16.
ieee: 'K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, “The complexity of partial-observation
stochastic parity games with finite-memory strategies,” presented at the FoSSaCS:
Foundations of Software Science and Computation Structures, Grenoble, France,
2014, vol. 8412, pp. 242–257.'
ista: 'Chatterjee K, Doyen L, Nain S, Vardi M. 2014. The complexity of partial-observation
stochastic parity games with finite-memory strategies. FoSSaCS: Foundations of
Software Science and Computation Structures, LNCS, vol. 8412, 242–257.'
mla: Chatterjee, Krishnendu, et al. The Complexity of Partial-Observation Stochastic
Parity Games with Finite-Memory Strategies. Vol. 8412, Springer, 2014, pp.
242–57, doi:10.1007/978-3-642-54830-7_16.
short: K. Chatterjee, L. Doyen, S. Nain, M. Vardi, in:, Springer, 2014, pp. 242–257.
conference:
end_date: 2014-04-13
location: Grenoble, France
name: 'FoSSaCS: Foundations of Software Science and Computation Structures'
start_date: 2014-04-05
date_created: 2018-12-11T11:56:21Z
date_published: 2014-04-01T00:00:00Z
date_updated: 2023-02-23T12:24:58Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-54830-7_16
ec_funded: 1
external_id:
arxiv:
- '1401.3289'
intvolume: ' 8412'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1401.3289
month: '04'
oa: 1
oa_version: Preprint
page: 242 - 257
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _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: '4757'
quality_controlled: '1'
related_material:
record:
- id: '5408'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: The complexity of partial-observation stochastic parity games with finite-memory
strategies
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8412
year: '2014'
...