A near-linear-time algorithm for weak bisimilarity on Markov chains.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)


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 log4 n), where n is the number of states and m the number of transitions. The algorithm in this article also can determine branching bisimulation for action-labelled fully probabilistic systems in the same time complexity. 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).
Originele taal-2Engels
Titel31st International Conference on Concurrency Theory (CONCUR2020)
RedacteurenIgor Konnov, Laura Kovacs
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's20
ISBN van elektronische versie9783959771603
StatusGepubliceerd - 1 aug. 2020

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
ISSN van geprinte versie1868-8969


Duik in de onderzoeksthema's van 'A near-linear-time algorithm for weak bisimilarity on Markov chains.'. Samen vormen ze een unieke vingerafdruk.

Citeer dit