License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2020.8
URN: urn:nbn:de:0030-drops-128209
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12820/
Jansen, David N. ;
Groote, Jan Friso ;
Timmers, Ferry ;
Yang, Pengfei
A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains
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 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).
BibTeX - Entry
@InProceedings{jansen_et_al:LIPIcs:2020:12820,
author = {David N. Jansen and Jan Friso Groote and Ferry Timmers and Pengfei Yang},
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 = {Igor Konnov and Laura Kov{\'a}cs},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12820},
URN = {urn:nbn:de:0030-drops-128209},
doi = {10.4230/LIPIcs.CONCUR.2020.8},
annote = {Keywords: Behavioural Equivalence, weak Bisimulation, Markov Chain}
}
|
Keywords: |
|
Behavioural Equivalence, weak Bisimulation, Markov Chain |
|
Collection: |
|
31st International Conference on Concurrency Theory (CONCUR 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
