A near-linear-time algorithm for weak bisimilarity on Markov chains.

This article improves the time bound for calculating the weak/branching bisimulation minimisation quotient on state-labelled discrete-time Markov chains from O(m n) to an expected-time O(m log4 n), where n is the number of states and m the number of transitions. The algorithm in this article also can determine branching bisimulation for action-labelled fully probabilistic systems in the same time complexity. It follows the ideas of Groote et al. (ACM ToCL 2017) in combination with an efficient algorithm to handle decremental strongly connected components (Bernstein et al., STOC 2019).