2026-07-23T16:35:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12820 2024-03-06T10:50:46Z ddc:004 open_access

A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains Jansen, David N. Groote, Jan Friso Timmers, Ferry Yang, Pengfei Behavioural Equivalence weak Bisimulation Markov Chain 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik David N. Jansen and Jan Friso Groote and Ferry Timmers and Pengfei Yang 2020 Is Part Of LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2020.8 urn:nbn:de:0030-drops-128209 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode