×

A space-efficient probabilistic simulation algorithm. (English) Zbl 1160.68432

van Breugel, Franck (ed.) et al., CONCUR 2008 – concurrency theory. 19th international conference, CONCUR 2008, Toronto, Canada, August 19–22, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85360-2/pbk). Lecture Notes in Computer Science 5201, 248-263 (2008).
Summary: 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 [D. Bustan and O. Grumberg, “Simulation based minimization”, Lect. Notes Comput. Sci. 1831, 255–270 (2000; Zbl 0963.68110)] 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.
For the entire collection see [Zbl 1149.68018].

MSC:

68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Citations:

Zbl 0963.68110
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baier, C.; Engelen, B.; Majster-Cederbaum, M. E., Deciding bisimilarity and similarity for probabilistic processes, J. Comput. Syst. Sci., 60, 1, 187-231 (2000) · Zbl 1073.68690
[2] Bogdoll, J.; Hermanns, H.; Zhang, L.; Suzuki, K.; Higashino, T.; Yasumoto, K.; El-Fakih, K., An experimental evaluation of probabilistic simulation, Formal Techniques for Networked and Distributed Systems - FORTE 2008, 37-52 (2008), Heidelberg: Springer, Heidelberg
[3] Bustan, D.; Grumberg, O.; McAllester, D., Simulation based minimization, Automated Deduction - CADE-17, 255-270 (2000), Heidelberg: Springer, Heidelberg · Zbl 0963.68110
[4] Courcoubetis, C.; Vardi, M. Y.; Wolper, P.; Yannakakis, M.; Clarke, E.; Kurshan, R. P., Memory efficient algorithms for the verification of temporal properties, Computer-Aided Verification, 233-242 (1991), Heidelberg: Springer, Heidelberg · Zbl 0765.68120
[5] Gallo, G.; Grigoriadis, M.; Tarjan, R., A fast parametric maximum flow algorithm and applications, SIAM J. Comput., 18, 1, 30-55 (1989) · Zbl 0679.68080
[6] Gentilini, R.; Piazza, C.; Policriti, A., From bisimulation to simulation: Coarsest partition problems, J. Autom. Reasoning, 31, 1, 73-103 (2003) · Zbl 1081.68052
[7] Henzinger, M.R., Henzinger, T.A., Kopke, P.W.: Computing simulations on finite and infinite graphs. In: FOCS, pp. 453-462 (1995) · Zbl 0938.68538
[8] Jonsson, B., Larsen, K.: Specification and refinement of probabilistic processes. In: LICS, pp. 266-277 (1991)
[9] Milner, R., Communication and Concurrency (1989), Englewood Cliffs: Prentice Hall, Englewood Cliffs · Zbl 0683.68008
[10] Paige, R.; Tarjan, R. E., Three partition refinement algorithms, SIAM J. Comput., 16, 6, 973-989 (1987) · Zbl 0654.68072
[11] Ranzato, F., Tapparo, F.: A new efficient simulation equivalence algorithm. In: LICS, pp. 171-180 (2007)
[12] Segala, R.; Lynch, N. A., Probabilistic simulations for probabilistic processes., Nord. J. Comput., 2, 2, 250-273 (1995) · Zbl 0839.68067
[13] Tan, L.; Cleaveland, R.; Margaria, T.; Yi, W., Simulation revisited, Tools and Algorithms for the Construction and Analysis of Systems, 480-495 (2001), Heidelberg: Springer, Heidelberg · Zbl 0986.68165
[14] van Glabbeek, R.J., Ploeger, B.: Correcting a space-efficient simulation algorithm. In: CAV 2008 (to appear, 2008) · Zbl 1155.68450
[15] Zhang, L.: Decision Algorithms for Probabilistic Simulations. PhD thesis, Universitätm des Saarlandes (2008)
[16] Zhang, L.; Hermanns, H.; Namjoshi, K. S.; Yoneda, T.; Higashino, T.; Okamura, Y., Deciding simulations on probabilistic automata, Automated Technology for Verification and Analysis, 207-222 (2007), Heidelberg: Springer, Heidelberg · Zbl 1141.68443
[17] Zhang, L.; Hermanns, H.; Eisenbrand, F.; Jansen, D. N.; Grumberg, O.; Huth, M., Flow faster: Efficient decision algorithms for probabilistic simulations, Tools and Algorithms for the Construction and Analysis of Systems, 155-169 (2007), Heidelberg: Springer, Heidelberg · Zbl 1186.68326
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.