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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

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).
Original languageEnglish
Title of host publication31st International Conference on Concurrency Theory (CONCUR2020)
EditorsIgor Konnov, Laura Kovacs
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages8:1-8:20
Number of pages20
ISBN (Electronic)9783959771603
DOIs
Publication statusPublished - 1 Aug 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume171
ISSN (Print)1868-8969

Keywords

  • Behavioural Equivalence
  • Markov Chain
  • Weak Bisimulation

Fingerprint

Dive into the research topics of 'A near-linear-time algorithm for weak bisimilarity on Markov chains.'. Together they form a unique fingerprint.

Cite this