[ZhangHEJ07] Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations Zhang, L.; Hermanns, H.; Eisenbrand, F. and Jansen, D. N. In Tools and Algorithms for the Construction and Analysis of Systems, 13th International Conference (TACAS), pages 155-169, Springer, Lecture Notes in Computer Science 4424, 2007.
Downloads: pdf, bibURL: Abstract. Abstraction techniques based on simulation relations have become an important and effective proof technique to avoid the infamous state space explosion problem. In the context of Markov chains, strong and weak simulation relations have been proposed [17,6], together with corresponding decision algorithms [3,5], but it is as yet unclear whether they can be used as effectively as their non-stochastic counterparts. This paper presents drastically improved algorithms to decide whether one (discrete- or continuous-time) Markov chain strongly or weakly simulates another. The key innovation is the use of parametric maximum flow techniques to amortize computations.