--- res: bibo_abstract: - "We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-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). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are \r\nEXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. @eng" bibo_authorlist: - foaf_Person: foaf_givenName: Krishnendu foaf_name: Chatterjee, Krishnendu foaf_surname: Chatterjee foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-4561-241X - foaf_Person: foaf_givenName: Laurent foaf_name: Doyen, Laurent foaf_surname: Doyen - foaf_Person: foaf_givenName: Sumit foaf_name: Nain, Sumit foaf_surname: Nain - foaf_Person: foaf_givenName: Moshe foaf_name: Vardi, Moshe foaf_surname: Vardi bibo_doi: 10.15479/AT:IST-2013-141-v1-1 dct_date: 2013^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/2664-1690 dct_language: eng dct_publisher: IST Austria@ dct_title: The complexity of partial-observation stochastic parity games with finite-memory strategies@ ...