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).
@InProceedings{jansen_et_al:LIPIcs.CONCUR.2020.8, author = {Jansen, David N. and Groote, Jan Friso and Timmers, Ferry and Yang, Pengfei}, title = {{A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains}}, booktitle = {31st International Conference on Concurrency Theory (CONCUR 2020)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-160-3}, ISSN = {1868-8969}, year = {2020}, volume = {171}, editor = {Konnov, Igor and Kov\'{a}cs, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.8}, URN = {urn:nbn:de:0030-drops-128209}, doi = {10.4230/LIPIcs.CONCUR.2020.8}, annote = {Keywords: Behavioural Equivalence, weak Bisimulation, Markov Chain} }
Feedback for Dagstuhl Publishing