zbMATH — the first resource for mathematics

Bisimulation minimisation mostly speeds up probabilistic model checking. (English) Zbl 1186.68296
Grumberg, Orna (ed.) et al., Tools and algorithms for the construction and analysis of systems. 13th international conference, TACAS 2007, held as part of the joint European conferences on theory and practice of software, ETAPS 2007, Braga, Portugal, March 24 – April 1, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-71208-4/pbk). Lecture Notes in Computer Science 4424, 87-101 (2007).
Summary: 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 to be checked.
For the entire collection see [Zbl 1116.68006].

68Q60 Specification and verification (program logics, model checking, etc.)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Full Text: DOI