--- _id: '5400' abstract: - lang: eng text: 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. alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Chmelik, Martin id: 3624234E-F248-11E8-B48F-1D18A9856A87 last_name: Chmelik - first_name: Mathieu full_name: Tracol, Mathieu id: 3F54FA38-F248-11E8-B48F-1D18A9856A87 last_name: Tracol citation: ama: Chatterjee K, Chmelik M, Tracol M. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria; 2013. doi:10.15479/AT:IST-2013-109-v1-1 apa: Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable about partially observable Markov decision processes with ω-regular objectives. IST Austria. https://doi.org/10.15479/AT:IST-2013-109-v1-1 chicago: Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-109-v1-1. ieee: K. Chatterjee, M. Chmelik, and M. Tracol, What is decidable about partially observable Markov decision processes with ω-regular objectives. IST Austria, 2013. ista: Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with ω-regular objectives, IST Austria, 41p. mla: Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria, 2013, doi:10.15479/AT:IST-2013-109-v1-1. short: K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013. date_created: 2018-12-12T11:39:07Z date_published: 2013-02-20T00:00:00Z date_updated: 2023-02-23T10:36:45Z day: '20' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2013-109-v1-1 file: - access_level: open_access checksum: cbba40210788a1b22c6cf06433b5ed6f content_type: application/pdf creator: system date_created: 2018-12-12T11:53:06Z date_updated: 2020-07-14T12:46:44Z file_id: '5467' file_name: IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf file_size: 483407 relation: main_file file_date_updated: 2020-07-14T12:46:44Z has_accepted_license: '1' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: '41' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '109' related_material: record: - id: '1477' relation: later_version status: public - id: '2295' relation: later_version status: public status: public title: What is decidable about partially observable Markov decision processes with ω-regular objectives type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ...