{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,11]],"date-time":"2026-10-11T02:56:00Z","timestamp":1791687360546,"version":"4.3.4"},"reference-count":29,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2018,9,3]],"date-time":"2018-09-03T00:00:00Z","timestamp":1535932800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We provide an algorithm to efficiently compute bisimulation for probabilistic labeled transition systems, featuring non-deterministic choice as well as discrete probabilistic choice. The algorithm is linear in the number of transitions and logarithmic in the number of states, distinguishing both action states and probabilistic states, and the transitions between them. The algorithm improves upon the proposed complexity bounds of the best algorithm addressing the same purpose so far by Baier, Engelen and Majster-Cederbaum (Journal of Computer and System Sciences 60:187\u2013231, 2000). In addition, experimentally, on various benchmarks, our algorithm performs rather well; even on relatively small transition systems, a performance gain of a factor 10,000 can be achieved.<\/jats:p>","DOI":"10.3390\/a11090131","type":"journal-article","created":{"date-parts":[[2018,9,3]],"date-time":"2018-09-03T10:50:51Z","timestamp":1535971851000},"page":"131","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["An Efficient Algorithm to Determine Probabilistic Bisimulation"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2196-6587","authenticated-orcid":false,"given":"Jan Friso","family":"Groote","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Eindhoven Universtiy of Technology, P.O. Box 512, 5600 MB Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jao","family":"Rivera Verduzco","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Eindhoven Universtiy of Technology, P.O. Box 512, 5600 MB Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9514-2260","authenticated-orcid":false,"given":"Erik P.","family":"De Vink","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Eindhoven Universtiy of Technology, P.O. Box 512, 5600 MB Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,9,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(91)90030-6","article-title":"Bisimulation through probabilistic testing","volume":"94","author":"Larsen","year":"1991","journal-title":"Inf. Comput."},{"key":"ref_2","unstructured":"Segala, R. (1995). Modeling and Verification of Randomized Distributed Real-Time Systems. [Ph.D. Thesis, Laboratory for Computer Science, Massachusetts Institute of Technology]."},{"key":"ref_3","first-page":"481","article-title":"Probabilistic Simulations for Probabilistic Processes","volume":"Volume 836","author":"Jonsson","year":"2005","journal-title":"CONCUR \u201994: Concurrency Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1999.1683","article-title":"Deciding bisimilarity and similarity for probabilistic processes","volume":"60","author":"Baier","year":"2000","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1137\/0216062","article-title":"Three partition refinement algorithms","volume":"16","author":"Paige","year":"1987","journal-title":"SIAM J. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Valmari, A., and Franceschinis, G. (2010, January 20\u201328). Simple O(mlogn) time Markov chain lumping. Proceedings of the 16th international conference on Tools and Algorithms for the Construction and Analysis of Systems, Paphos, Cyprus.","DOI":"10.1007\/978-3-642-12002-2_4"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S0020-0190(03)00343-0","article-title":"Optimal state-space lumping in Markov chains","volume":"87","author":"Dersavi","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_8","unstructured":"Kwiatkowska, M., Norman, G., and Parker, D. (June, January 28). Stochastic model checking. Proceedings of the 7th international conference on Formal methods for performance evaluation, Bertinoro, Italy."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Groote, J.F., and Mousavi, M.R. (2014). Modeling and Analysis of Communication Systems, The MIT Press.","DOI":"10.7551\/mitpress\/9946.001.0001"},{"key":"ref_10","first-page":"199","article-title":"An Overview of the mCRL2 Toolset and Its Recent Advances","volume":"Volume 7795","author":"Piterman","year":"2013","journal-title":"Tools and Algorithms for the Construction and Analysis of Systems"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1007\/BF01211866","article-title":"A logic for reasoning about time and reliability","volume":"6","author":"Hansson","year":"1994","journal-title":"Formal Aspects Comput."},{"key":"ref_12","first-page":"87","article-title":"Bisimulation Minimisation Mostly Speeds Up Probabilistic Model Checking","volume":"Volume 4424","author":"Grumberg","year":"2007","journal-title":"Tools and Algorithms for the Construction and Analysis of Systems"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/978-3-642-35873-9_5","article-title":"SMT-based bisimulation Minimisation of Markov Models","volume":"Volume 7737","author":"Giacobazzi","year":"2013","journal-title":"Verification, Model Checking, and Abstract Interpretation"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2627352","article-title":"Incremental bisimulation abstraction refinement","volume":"13","author":"Song","year":"2014","journal-title":"ACM Trans. Embedded Comput. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Hillston, J., Marin, A., Rossi, S., and Piazza, C. (2013, January 10\u201312). Contextual lumpability. Proceedings of the 7th International Conference on Performance Evaluation Methodologies and Tools, Torino, Italy.","DOI":"10.4108\/icst.valuetools.2013.254408"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1007\/s10703-012-0147-3","article-title":"Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation","volume":"40","author":"Crafa","year":"2012","journal-title":"Formal Methods Syst. Des."},{"key":"ref_17","unstructured":"Dorsch, U., Milius, S., Schr\u00f6der, L., and Wissmann, T. (arXiv, 2017). Efficient coalgebraic partition refinement, arXiv."},{"key":"ref_18","first-page":"1","article-title":"Flow faster: efficient decision algorithms for probabilistic simulations","volume":"4","author":"Zhang","year":"2008","journal-title":"Logical Methods Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.ic.2016.04.002","article-title":"A space-efficient simulation algorithm on probabilistic automata","volume":"249","author":"Zhang","year":"2016","journal-title":"Inf. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/3-540-45694-5_25","article-title":"Decision Algorithms for Probabilistic Bisimulation","volume":"Volume 2421","author":"Brim","year":"2002","journal-title":"CONCUR 2002 \u2014 Concurrency Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.ic.2015.07.004","article-title":"Polynomial time decision algorithms for probabilistic automata","volume":"244","author":"Turrini","year":"2015","journal-title":"Inf. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1007\/s00165-012-0242-7","article-title":"Exploring probabilistic bisimulations, part I","volume":"24","author":"Hennessy","year":"2012","journal-title":"Formal Aspects Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0890-5401(90)90025-D","article-title":"CCS expressions, finite state processes and three problems of equivalence","volume":"86","author":"Kannelakis","year":"1990","journal-title":"Inf. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3060140","article-title":"An O(mlogn) algorithm for computing stuttering equivalence and branching bisimulation","volume":"18","author":"Groote","year":"2017","journal-title":"ACM Trans. Comput. Logic"},{"key":"ref_25","first-page":"319","article-title":"Simple bisimilarity minimization in O(mlogn) time","volume":"105","author":"Valmari","year":"2010","journal-title":"Fundam. Inf."},{"key":"ref_26","unstructured":"Baier, C. Personal communication."},{"key":"ref_27","unstructured":"Antonick, G. (2013, August 12). Ant on a grid. Available online: http:\/\/wordplay.blogs.nytimes.com\/\/2013\/08\/12\/ants-2\/."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/978-3-319-68270-9_3","article-title":"Problem Solving Using Process Algebra Considered Insightful","volume":"Volume 10500","author":"Katoen","year":"2017","journal-title":"ModelEd, TestEd, TrustEd. Lecture Notes in Computer Science"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Bandini, E., and Segala, R. (2001, January 8\u201312). Axiomatizations for probabilistic bisimulation. Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP) 2001, Crete, Greece.","DOI":"10.1007\/3-540-48224-5_31"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/9\/131\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:18:34Z","timestamp":1760195914000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/9\/131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,3]]},"references-count":29,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2018,9]]}},"alternative-id":["a11090131"],"URL":"https:\/\/doi.org\/10.3390\/a11090131","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,3]]}}}