@inproceedings{2295, 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.}, author = {Chatterjee, Krishnendu and Chmelik, Martin and Tracol, Mathieu}, location = {Torino, Italy}, pages = {165 -- 180}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{What is decidable about partially observable Markov decision processes with omega-regular objectives}}, doi = {10.4230/LIPIcs.CSL.2013.165}, volume = {23}, year = {2013}, }