An O(m log n) algorithm for branching bisimilarity on labelled transition systems

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

Branching bisimilarity is a behavioural equivalence relation on labelled transition systems (LTSs) that takes internal actions into account. It has the traditional advantage that algorithms for branching bisimilarity are more efficient than ones for other weak behavioural equivalences, especially weak bisimilarity. With m the number of transitions and n the number of states, the classic O(mn) algorithm was recently replaced by an O(m(log |Act| + log n) algorithm, which is unfortunately rather complex. This paper combines its ideas with the ideas from Valmari resulting in a simpler O(m log n) algorithm.

Originele taal-2Engels
TitelTools and Algorithms for the Construction and Analysis of Systems- 26th International Conference, TACAS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Proceedings, Part II
RedacteurenArmin Biere, David Parker
UitgeverijSpringer
Pagina's3-20
Aantal pagina's18
ISBN van geprinte versie9783030452360
DOI's
StatusGepubliceerd - 1 jan 2020
Evenement26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020 - Dublin, Ierland
Duur: 25 apr 202030 apr 2020

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12079 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020
LandIerland
StadDublin
Periode25/04/2030/04/20

Vingerafdruk Duik in de onderzoeksthema's van 'An O(m log n) algorithm for branching bisimilarity on labelled transition systems'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Jansen, D. N., Groote, J. F., Keiren, J. J. A., & Wijs, A. (2020). An O(m log n) algorithm for branching bisimilarity on labelled transition systems. In A. Biere, & D. Parker (editors), Tools and Algorithms for the Construction and Analysis of Systems- 26th International Conference, TACAS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Proceedings, Part II (blz. 3-20). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12079 LNCS). Springer. https://doi.org/10.1007/978-3-030-45237-7_1