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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

45 Downloads (Pure)

Samenvatting

Branching bisimilarity is a behavioural equivalence relation on labelled transition systems that takes internal actions into account. It has the traditional advantage that algorithms for branching bisimilarity are more efficient than all algorithms 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 has recently been replaced by an O(m log n) algorithm, which is unfortunately rather complex. This paper combines the ideas from Groote et al. with the ideas from Valmari. This results in a simpler O(m log n) algorithm. Benchmarks show that this new algorithm is faster and more memory efficient than all its predecessors.
Originele taal-2Engels
Artikelnummer1909.10824
Aantal pagina's27
TijdschriftarXiv
Volume2019
DOI's
StatusGepubliceerd - 24 sep. 2019

Bibliografische nota

Also appeared as CSR-19-03

Vingerafdruk

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

Citeer dit