Probabilistic systems with limsup and liminf objectives Conference Paper


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A
Title: Probabilistic systems with limsup and liminf objectives
Title Series: LNCS
Affiliation
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.
Conference Title: ILC: Infinity in Logic and Computation
Volume: 5489
Conference Dates: November 3-5, 2007
Conference Location: Cape Town, South Africa
ISBN: 3-642-03091-2
Publisher: Springer  
Location: Berlin, Heidelberg
Date Published: 2009-12-15
Start Page: 32
End Page: 45
URL:
DOI: 10.1007/978-3-642-03092-5_4
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work