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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)

Samenvatting

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
Pagina's8:1-8:20
Aantal pagina's20
ISBN van elektronische versie9783959771603
DOI's
StatusGepubliceerd - 1 aug. 2020

Publicatie series

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

Financiering

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.

FinanciersFinanciernummer
National Natural Science Foundation of China61761136011, 61532019
Chinese Academy of Sciences

    Vingerafdruk

    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