A Space-Efficient Probabilistic Simulation Algorithm
In Concurrency Theory, 19th International Conference (CONCUR)
, pages 248-263, Springer
, Lecture Notes in Computer Science 5201, 2008.
Downloads: pdf, bibURL: http://dx.doi.org/10.1007/978-3-540-85361-9_22
Abstract. In the context of probabilistic automata, time efficient algorithms for probabilistic simulations have been proposed lately. The space complexity thereof is quadratic in the size of the transition relation, thus space requirements often become the practical bottleneck. In this paper, we exploit ideas from  to arrive at a space-efficient algorithm for computing probabilistic simulations based on partition refinement. Experimental evidence is given that not only the space-efficiency is improved drastically. The experiments often require orders of magnitude less time.