This paper studies the effect of bisimulation minimisation in model checking of monolithic discrete-time and continuous-time Markov chains as well as variants thereof with rewards. Our results show that--as for traditional model checking--enormous state space reductions (up to logarithmic savings) may be obtained. In contrast to traditional model checking, in many cases, the verification time of the original Markov chain exceeds the quotienting time plus the verification time of the quotient. We consider probabilistic bisimulation as well as versions thereof that are tailored to the property be checked.
|Name||Lecture Notes in Computer Science|
|Name||Theoretical Computer Science and General Issues|
|Conference||13th International Conference on Tools and Algorithms for Construction and Analysis of Systems, TACAS 2007|
|Period||24/03/07 → 1/04/07|