摘要：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).
