thesis published Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Martin Chmelik author 3624234E-F248-11E8-B48F-1D18A9856A87 Mathieu Tracol author 3F54FA38-F248-11E8-B48F-1D18A9856A87 KrCh department We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied 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 complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish asymptotically optimal (exponential) memory bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. https://research-explorer.ista.ac.at/download/5400/5467/IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf application/pdfno IST Austria2013 eng 2664-169010.15479/AT:IST-2013-109-v1-1 41 https://research-explorer.ista.ac.at/record/2295 https://research-explorer.ista.ac.at/record/1477 K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013. Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013. <a href="https://doi.org/10.15479/AT:IST-2013-109-v1-1">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>. Chatterjee, Krishnendu, et al. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013, doi:<a href="https://doi.org/10.15479/AT:IST-2013-109-v1-1">10.15479/AT:IST-2013-109-v1-1</a>. K. Chatterjee, M. Chmelik, and M. Tracol, <i>What is decidable about partially observable Markov decision processes with ω-regular objectives</i>. IST Austria, 2013. Chatterjee, K., Chmelik, M., &#38; Tracol, M. (2013). <i>What is decidable about partially observable Markov decision processes with ω-regular objectives</i>. IST Austria. <a href="https://doi.org/10.15479/AT:IST-2013-109-v1-1">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a> Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with ω-regular objectives, IST Austria, 41p. Chatterjee K, Chmelik M, Tracol M. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria; 2013. doi:<a href="https://doi.org/10.15479/AT:IST-2013-109-v1-1">10.15479/AT:IST-2013-109-v1-1</a> 54002018-12-12T11:39:07Z2025-09-18T11:38:38Z