文章基本信息

标题：A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains
本地全文：下载
作者：David N. Jansen ; Jan Friso Groote ; Ferry Timmers 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：171
页码：8:1-8:20
DOI：10.4230/LIPIcs.CONCUR.2020.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：Behavioural Equivalence; weak Bisimulation; Markov Chain