@inproceedings{c93b850be48b44fe8220eeb1577f6b92,
title = "A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions",
abstract = "The most efficient way to calculate strong bisimilarity is by finding the relational coarsest partition of a transition system. We provide the first linear-time algorithm to calculate strong bisimulation using parallel random access machines (PRAMs). More precisely, with n states, m transitions and | Act| ≤ m action labels, we provide an algorithm for max (n, m) processors that calculates strong bisimulation in time O(n+ | Act| ) and space O(n+ m). The best-known PRAM algorithm has time complexity O(nlog n) on a smaller number of processors making it less suitable for massive parallel devices such as GPUs. An implementation on a GPU shows that the linear time-bound is achievable on contemporary hardware.",
keywords = "Bisimulation, Relational Coarsest Partition",
author = "Jan Martens and Groote, \{Jan Friso\} and \{van den Haak\}, Lars and Pieter Hijma and Anton Wijs",
year = "2021",
month = oct,
day = "28",
doi = "10.1007/978-3-030-90636-8\_7",
language = "English",
isbn = "978-3-030-90635-1",
series = "Lecture Notes in Computer Science (LNCS)",
publisher = "Springer",
pages = "115--133",
editor = "Gwen Sala{\"u}n and Anton Wijs",
booktitle = "Formal Aspects of Component Software",
address = "Germany",
note = "17th International Conference on Formal Aspects of Component Software, FACS 2021 ; Conference date: 28-10-2021 Through 29-10-2021",
}