Abstract

Probabilistic model checking is a technique for the verification of probabilistic systems. The size of the state space is a limiting factor for model checking. We used bisimulation minimisation to combat this problem. Bisimulation minimisation is a technique where the model under consideration is first minimised prior to the actual model checking. We also considered a technique where the model is minimised for a specific property, called formula-dependent lumping. The minimisation algorithm has been implemented into the model checker MRMC.

Using case studies, we empirically studied the effectiveness of bisimulation minimisation for probabilistic model checking. The probabilistic models we consider are discrete-time Markov chains and continuous-time Markov chains. Properties are expressed in the temporal logic PCTL or CSL. Our experiments showed that bisimulation minimisation can result into large state space reductions. Formula-dependent lumping can lead to even larger state space reductions. For several cases, minimising the original model plus checking the minimised model is faster than model checking the original model. We conclude that bisimulation minimisation is a good state space reduction technique.

Additional Resources

1. The paper