TY - JOUR
T1 - Linear parallel algorithms to compute strong and branching bisimilarity
AU - Martens, Jan
AU - Groote, Jan Friso
AU - Haak, Lars B.van den
AU - Hijma, Pieter
AU - Wijs, Anton
N1 - Publisher Copyright:
© 2022, The Author(s).
PY - 2023/4
Y1 - 2023/4
N2 - We present the first parallel algorithms that decide strong and branching bisimilarity in linear time. More precisely, if a transition system has n states, m transitions and | Act| action labels, we introduce an algorithm that decides strong bisimilarity in O(n+ | Act|) time on max (n, m) processors and an algorithm that decides branching bisimilarity in O(n+ | Act|) time using up to max (n2, m, | Act| n) processors.
AB - We present the first parallel algorithms that decide strong and branching bisimilarity in linear time. More precisely, if a transition system has n states, m transitions and | Act| action labels, we introduce an algorithm that decides strong bisimilarity in O(n+ | Act|) time on max (n, m) processors and an algorithm that decides branching bisimilarity in O(n+ | Act|) time using up to max (n2, m, | Act| n) processors.
KW - Branching bisimulation
KW - Parallel algorithms
KW - PRAM
KW - RCPP
KW - Strong bisimulation
UR - http://www.scopus.com/inward/record.url?scp=85143387594&partnerID=8YFLogxK
U2 - 10.1007/s10270-022-01060-7
DO - 10.1007/s10270-022-01060-7
M3 - Article
AN - SCOPUS:85143387594
SN - 1619-1366
VL - 22
SP - 521
EP - 545
JO - Software and Systems Modeling
JF - Software and Systems Modeling
IS - 2
ER -