[{"date_updated":"2023-02-23T11:23:11Z","ddc":[],"creator":{"login":"dernst","id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},"file_date_updated":"2020-07-14T12:46:41Z","department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"KrCh"}],"_id":"5387","type":"technical_report","pubrep_id":"23","status":"public","publication_status":"published","publication_identifier":{"issn":[]},"language":[{}],"file":[{"file_id":"5458","checksum":"824d6c70e6d3feb3e836b009e0b3cf73","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"IST-2011-0001_IST-2011-0001.pdf","date_created":"2018-12-12T11:52:57Z","creator":"system","file_size":329976,"date_updated":"2020-07-14T12:46:41Z"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"3345"}]},"abstract":[{"lang":"eng"}],"oa_version":"Published Version","alternative_title":[],"month":"02","citation":{"ista":"Chatterjee K, Doyen L. 2011. Energy and mean-payoff parity Markov decision processes, IST Austria, 20p.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. Energy and Mean-Payoff Parity Markov Decision Processes. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0001.","apa":"Chatterjee, K., & Doyen, L. (2011). Energy and mean-payoff parity Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2011-0001","ieee":"K. Chatterjee and L. Doyen, Energy and mean-payoff parity Markov decision processes. IST Austria, 2011.","short":"K. Chatterjee, L. Doyen, Energy and Mean-Payoff Parity Markov Decision Processes, IST Austria, 2011.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. Energy and Mean-Payoff Parity Markov Decision Processes. IST Austria, 2011, doi:10.15479/AT:IST-2011-0001."},"dini_type":"doc-type:other","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Laurent","last_name":"Doyen"}],"has_accepted_license":"1","dc":{"title":["Energy and mean-payoff parity Markov decision processes","IST Austria Technical Report"],"subject":["ddc:000","ddc:005"],"creator":["Chatterjee, Krishnendu","Doyen, Laurent"],"language":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"type":["info:eu-repo/semantics/other","doc-type:other","text","http://purl.org/coar/resource_type/c_1843"],"publisher":["IST Austria"],"date":["2011"],"identifier":["https://research-explorer.ista.ac.at/record/5387","https://research-explorer.ista.ac.at/download/5387/5458"],"description":["We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition re- quires that the resource level never drops below 0, and the mean-payoff condi- tion requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound."],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.15479/AT:IST-2011-0001","info:eu-repo/semantics/altIdentifier/issn/2664-1690"],"source":["Chatterjee K, Doyen L. Energy and Mean-Payoff Parity Markov Decision Processes. IST Austria; 2011. doi:10.15479/AT:IST-2011-0001"]},"day":"16","page":"20","uri_base":"https://research-explorer.ista.ac.at","date_created":"2018-12-12T11:39:02Z","date_published":"2011-02-16T00:00:00Z","oa":1}]