Model Checking Interactive Markov Chains
In Tools and Algorithms for the Construction and Analysis of Systems, 16th International Conference (TACAS)
, pages 53-68, Springer
, Lecture Notes in Computer Science 6015, 2010.
Downloads: pdf, bibURL: http://dx.doi.org/10.1007/978-3-642-12002-2_5
Abstract. Hermanns has introduced interactive Markov chains (IMCs) which arise as an orthogonal extension of labelled transition systems and continuous-time Markov chains (CTMCs). IMCs enjoy nice compositional aggregation properties which help to minimize the state space incrementally. However, the model checking problem for IMCs remains unsolved apart from those instances, where the IMC can be converted into a CTMC. This paper tackles this problem: We interpret the continuous stochastic logic (CSL) over IMCs and define the semantics of probabilistic CSL formulas with respect to the class of fully time and history dependent schedulers. Our main contribution is an efficient model checking algorithm for verifying CSL formulas on IMCs. Moreover, we show the applicability of our approach and provide some experimental results.