Probabilistic systems with limsup and liminf objectives
Chatterjee K, Henzinger TA. 2009. Probabilistic systems with limsup and liminf objectives. ILC: Infinity in Logic and Computation, LNCS, vol. 5489, 32–45.
Download (ext.)
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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar