Tags:Algorithm, Branching bisimulation, Markov chain and Weak bisimulation

Abstract:

This article improves the time bound for calculating the weak/branching bisimulation minimisation quotient on state-labelled discrete-time Markov chains from O(mn) to an expected-time O(m log^{4}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^{4}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).

A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains