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 log? n), where n is the number of states and m the number of transitions. For these results we assume that the set of state labels AP is small (|AP| ? O(m/n log? n)). 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)