[{"abstract":[{"lang":"eng"}],"alternative_title":[],"type":"conference","file":[{"file_name":"IST-2017-756-v1+1_2.pdf","access_level":"open_access","file_size":345171,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"4766","date_updated":"2020-07-14T12:45:37Z","date_created":"2018-12-12T10:09:42Z","checksum":"ba2828322955574d9283bea0e17a37a6"}],"oa_version":"Published Version","pubrep_id":"756","intvolume":" 23","status":"public","ddc":[],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2295","uri_base":"https://research-explorer.ista.ac.at","has_accepted_license":"1","day":"27","series_title":"Leibniz International Proceedings in Informatics","dc":{"language":["eng"],"date":["2013"],"title":["What is decidable about partially observable Markov decision processes with omega-regular objectives","LIPIcs"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.CSL.2013.165","info:eu-repo/grantAgreement/FWF//P 23499-N23","info:eu-repo/grantAgreement/FWF//S11407","info:eu-repo/grantAgreement/EC/FP7/279307"],"subject":["ddc:000"],"publisher":["Schloss Dagstuhl - Leibniz-Zentrum für Informatik"],"source":["Chatterjee K, Chmelik M, Tracol M. What is decidable about partially observable Markov decision processes with omega-regular objectives. 2013;23:165-180. doi:10.4230/LIPIcs.CSL.2013.165"],"rights":["https://creativecommons.org/licenses/by/4.0/","info:eu-repo/semantics/openAccess"],"creator":["Chatterjee, Krishnendu","Chmelik, Martin","Tracol, Mathieu"],"description":["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."],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"identifier":["https://research-explorer.ista.ac.at/record/2295","https://research-explorer.ista.ac.at/download/2295/4766"]},"scopus_import":1,"date_published":"2013-08-27T00:00:00Z","page":"165 - 180","citation":{"mla":"Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable Markov Decision Processes with Omega-Regular Objectives. Vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 165–80, doi:10.4230/LIPIcs.CSL.2013.165.","short":"K. Chatterjee, M. Chmelik, M. Tracol, 23 (2013) 165–180.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. “What Is Decidable about Partially Observable Markov Decision Processes with Omega-Regular Objectives.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.165.","ista":"Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with omega-regular objectives. 23, 165–180.","apa":"Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable about partially observable Markov decision processes with omega-regular objectives. Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2013.165","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, “What is decidable about partially observable Markov decision processes with omega-regular objectives,” vol. 23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 165–180, 2013."},"creator":{"login":"dernst","id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},"ec_funded":1,"publist_id":"4633","file_date_updated":"2020-07-14T12:45:37Z","volume":23,"dini_type":"doc-type:conferenceObject","date_created":"2018-12-11T11:56:50Z","date_updated":"2023-02-23T12:24:38Z","related_material":{"record":[{"id":"1477","status":"public","relation":"later_version"},{"status":"public","relation":"earlier_version","id":"5400"}]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik"},{"first_name":"Mathieu","last_name":"Tracol","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87"}],"department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"KrCh"}],"publication_status":"published","month":"08","language":[{}],"conference":{"end_date":"2013-09-05","start_date":"2013-09-02","location":"Torino, Italy","name":"CSL: Computer Science Logic"},"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"}}]