Model-checking omega-regular properties of interval Markov chains

K. Chatterjee, T.A. Henzinger, K. Sen, in:, Springer, 2008, pp. 302–317.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Series Title
LNCS
Abstract
We study the problem of model checking Interval-valued Discrete-time Markov Chains (IDTMC). IDTMCs are discrete-time finite Markov Chains for which the exact transition probabilities are riot known. Instead in IDTMCs, each transition is associated with an interval in which the actual transition probability must lie. We consider two semantic interpretations for the uncertainty in the transition probabilities of an IDTMC. In the first interpretation, we think of an IDTMC as representing a (possibly uncountable) family of (classical) discrete-time Markov Chains, where each member of the family is a Markov Chain whose transition probabilities lie within the interval range given in the IDTMC. We call this semantic interpretation Uncertain Markov Chains (UMC). In the second semantics for an IDTMC, which we call Interval Markov Decision Process (IMDP), we view the uncertainty as being resolved through non-determinism. In other words, each time a state is visited, we adversarially pick a transition distribution that respects the interval constraints, and take a probabilistic step according to the chosen distribution. We introduce a logic omega-PCTL that can express liveness, strong fairness, and omega-regular properties (such properties cannot be expressed in PCTL). We show that the omega-PCTL model checking problem for Uncertain Markov Chain semantics is decidable in PSPACE (same as the best known upper bound for PCTL) and for Interval Markov Decision Process semantics is decidable in coNP (improving the previous known PSPACE bound for PCTL). We also show that the qualitative fragment of the logic can lie solved in coNP for the UMC interpretation, and can be solved in polynomial time for a sub-class of UMCs. We also prove lower bounds for these model checking problems. We show that the model checking problem of IDTMCs with LTL formulas can be solved for both UMC and IMDP semantics by reduction to the model checking problem of IDTMC with omega-PcTL formulas.
Publishing Year
Date Published
2008-03-01
Volume
4962
Page
302 - 317
Conference
FoSSaCS: Foundations of Software Science and Computation Structures
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA, Sen K. Model-checking omega-regular properties of interval Markov chains. In: Vol 4962. Springer; 2008:302-317. doi:10.1007/978-3-540-78499-9_22
Chatterjee, K., Henzinger, T. A., & Sen, K. (2008). Model-checking omega-regular properties of interval Markov chains (Vol. 4962, pp. 302–317). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Springer. https://doi.org/10.1007/978-3-540-78499-9_22
Chatterjee, Krishnendu, Thomas A Henzinger, and Koushik Sen. “Model-Checking Omega-Regular Properties of Interval Markov Chains,” 4962:302–17. Springer, 2008. https://doi.org/10.1007/978-3-540-78499-9_22.
K. Chatterjee, T. A. Henzinger, and K. Sen, “Model-checking omega-regular properties of interval Markov chains,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, 2008, vol. 4962, pp. 302–317.
Chatterjee K, Henzinger TA, Sen K. 2008. Model-checking omega-regular properties of interval Markov chains. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 4962. 302–317.
Chatterjee, Krishnendu, et al. Model-Checking Omega-Regular Properties of Interval Markov Chains. Vol. 4962, Springer, 2008, pp. 302–17, doi:10.1007/978-3-540-78499-9_22.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar