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

David Jansen; Jan Friso Groote; Ferry Timmers; Pengfei Yang

doi:10.4230/LIPIcs.CONCUR.2020.8

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

David Jansen, Jan Friso Groote, Ferry Timmers, Pengfei Yang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (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 log⁴ 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 language	English
Title of host publication	31st International Conference on Concurrency Theory (CONCUR2020)
Editors	Igor Konnov, Laura Kovacs
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	8:1-8:20
Number of pages	20
ISBN (Electronic)	9783959771603
DOIs	https://doi.org/10.4230/LIPIcs.CONCUR.2020.8
Publication status	Published - 1 Aug 2020

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	171
ISSN (Print)	1868-8969

Funding

Funding David N. Jansen: This research is partly done during a visit to Eindhoven University of Technology, The Netherlands. This author is supported by the National Natural Science Foundation of China, Grants No. 61761136011 and 61532019. Jan Friso Groote: This research is partly done during a visit to the State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, P.R. China. This research is partly done during a visit to Eindhoven University of Technology, The Netherlands. This author is supported by the National Natural Science Foundation of China, Grants No. 61761136011 and 61532019. This research is partly done during a visit to the State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, P.R. China.

Funders	Funder number
National Natural Science Foundation of China	61761136011, 61532019
Chinese Academy of Sciences

Keywords

Behavioural Equivalence
Markov Chain
Weak Bisimulation

Access to Document

10.4230/LIPIcs.CONCUR.2020.8

Cite this

Jansen, D., Groote, J. F., Timmers, F., & Yang, P. (2020). A near-linear-time algorithm for weak bisimilarity on Markov chains. In I. Konnov, & L. Kovacs (Eds.), 31st International Conference on Concurrency Theory (CONCUR2020) (pp. 8:1-8:20). Article 8 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 171). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2020.8

Jansen, David ; Groote, Jan Friso ; Timmers, Ferry et al. / A near-linear-time algorithm for weak bisimilarity on Markov chains. 31st International Conference on Concurrency Theory (CONCUR2020). editor / Igor Konnov ; Laura Kovacs. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. pp. 8:1-8:20 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{b61095dcc86e497d9fef8ffc97a4188f,

title = "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 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).",

keywords = "Behavioural Equivalence, Markov Chain, Weak Bisimulation",

author = "David Jansen and Groote, {Jan Friso} and Ferry Timmers and Pengfei Yang",

year = "2020",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.CONCUR.2020.8",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "8:1--8:20",

editor = "Igor Konnov and Laura Kovacs",

booktitle = "31st International Conference on Concurrency Theory (CONCUR2020)",

}

Jansen, D , Groote, JF , Timmers, F & Yang, P 2020, A near-linear-time algorithm for weak bisimilarity on Markov chains. in I Konnov & L Kovacs (eds), 31st International Conference on Concurrency Theory (CONCUR2020)., 8, Leibniz International Proceedings in Informatics, LIPIcs, vol. 171, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, pp. 8:1-8:20. https://doi.org/10.4230/LIPIcs.CONCUR.2020.8

A near-linear-time algorithm for weak bisimilarity on Markov chains. / Jansen, David ; Groote, Jan Friso ; Timmers, Ferry et al.
31st International Conference on Concurrency Theory (CONCUR2020). ed. / Igor Konnov; Laura Kovacs. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. p. 8:1-8:20 8 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 171).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Jansen, David

AU - Groote, Jan Friso

AU - Timmers, Ferry

AU - Yang, Pengfei

PY - 2020/8/1

Y1 - 2020/8/1

N2 - 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).

AB - 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).

KW - Behavioural Equivalence

KW - Markov Chain

KW - Weak Bisimulation

UR - http://www.scopus.com/inward/record.url?scp=85091602782&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CONCUR.2020.8

DO - 10.4230/LIPIcs.CONCUR.2020.8

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 8:1-8:20

BT - 31st International Conference on Concurrency Theory (CONCUR2020)

A2 - Konnov, Igor

A2 - Kovacs, Laura

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

ER -

Jansen D , Groote JF , Timmers F, Yang P. A near-linear-time algorithm for weak bisimilarity on Markov chains. In Konnov I, Kovacs L, editors, 31st International Conference on Concurrency Theory (CONCUR2020). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2020. p. 8:1-8:20. 8. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.CONCUR.2020.8

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

Abstract

Publication series

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this