--- res: bibo_abstract: - We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The qualitative analysis problem given a POMDP 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, we establish decidability (with optimal EXPTIME-complete complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite-memory strategies. We also establish asymptotically optimal (exponential) memory bounds.@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: Martin foaf_name: Chmelik, Martin foaf_surname: Chmelik foaf_workInfoHomepage: http://www.librecat.org/personId=3624234E-F248-11E8-B48F-1D18A9856A87 - foaf_Person: foaf_givenName: Mathieu foaf_name: Tracol, Mathieu foaf_surname: Tracol foaf_workInfoHomepage: http://www.librecat.org/personId=3F54FA38-F248-11E8-B48F-1D18A9856A87 bibo_doi: 10.4230/LIPIcs.CSL.2013.165 bibo_volume: 23 dct_date: 2013^xs_gYear dct_language: eng dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@ dct_title: What is decidable about partially observable Markov decision processes with omega-regular objectives@ ...