Probabilistic systems with limsup and liminf objectives

K. Chatterjee, T.A. Henzinger, in:, Springer, 2009, pp. 32–45.


Conference Paper | Published
Series Title
LNCS
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.
Publishing Year
Date Published
2009-12-15
Volume
5489
Page
32 - 45
Conference
ILC: Infinity in Logic and Computation
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA. Probabilistic systems with limsup and liminf objectives. In: Vol 5489. Springer; 2009:32-45. doi:10.1007/978-3-642-03092-5_4
Chatterjee, K., & Henzinger, T. A. (2009). Probabilistic systems with limsup and liminf objectives (Vol. 5489, pp. 32–45). Presented at the ILC: Infinity in Logic and Computation, Springer. https://doi.org/10.1007/978-3-642-03092-5_4
Chatterjee, Krishnendu, and Thomas A Henzinger. “Probabilistic Systems with Limsup and Liminf Objectives,” 5489:32–45. Springer, 2009. https://doi.org/10.1007/978-3-642-03092-5_4.
K. Chatterjee and T. A. Henzinger, “Probabilistic systems with limsup and liminf objectives,” presented at the ILC: Infinity in Logic and Computation, 2009, vol. 5489, pp. 32–45.
Chatterjee K, Henzinger TA. 2009. Probabilistic systems with limsup and liminf objectives. ILC: Infinity in Logic and Computation, LNCS, vol. 5489. 32–45.
Chatterjee, Krishnendu, and Thomas A. Henzinger. Probabilistic Systems with Limsup and Liminf Objectives. Vol. 5489, Springer, 2009, pp. 32–45, doi:10.1007/978-3-642-03092-5_4.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar