--- _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' ...