PT Journal
AU Della Penna, G
Intrigila, B
Melatti, I
Tronci, E
Venturini Zilli, M
TI Finite horizon analysis of Markov Chains with the Mur$\varphi$ verifier
SO Int. J. Softw. Tools Technol. Transf.
PY 2006
BP 397
EP 409
VL 8
IS 4
DI 10.1007/s10009-005-0216-7
AB In this paper we present an explicit disk-based verification algorithm for Probabilistic Systems defining discrete time/finite state Markov Chains. Given a Markov Chain and an integer k (horizon), our algorithm checks whether the probability of reaching an error state in at most k steps is below a given threshold. We present an implementation of our algorithm within a suitable extension of the Mur$\varphi$ verifier. We call the resulting probabilistic model checker FHP-Mur$\varphi$ (Finite Horizon Probabilistic Mur$\varphi$). We present experimental results comparing FHP-Mur$\varphi$ with (a finite horizon subset of) PRISM, a state-of-the-art symbolic model checker for Markov Chains. Our experimental results show that FHP-Mur$\varphi$ can handle systems that are out of reach for PRISM, namely those involving arithmetic operations on the state variables (e.g. hybrid systems).
PI Berlin, Heidelberg
ER