--- res: bibo_abstract: - We give polynomial-time algorithms for computing the values of Markov decision processes (MDPs) with limsup and liminf objectives. A real-valued reward is assigned to each state, and the value of an infinite path in the MDP is the limsup (resp. liminf) of all rewards along the path. The value of an MDP is the maximal expected value of an infinite path that can be achieved by resolving the decisions of the MDP. Using our result on MDPs, we show that turn-based stochastic games with limsup and liminf objectives can be solved in NP ∩ coNP. @eng bibo_authorlist: - foaf_Person: foaf_givenName: Krishnendu foaf_name: Krishnendu Chatterjee foaf_surname: Chatterjee foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-4561-241X - foaf_Person: foaf_givenName: Thomas A foaf_name: Thomas Henzinger foaf_surname: Henzinger foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87 orcid: 0000−0002−2985−7724 bibo_doi: 10.1007/978-3-642-03092-5_4 bibo_volume: 5489 dct_date: 2009^xs_gYear dct_publisher: Springer@ dct_title: Probabilistic systems with limsup and liminf objectives@ ...