# A linear parallel algorithm to compute bisimulation and relational coarsest partitions

arXiv: https://arxiv.org/abs/2105.11788 · HTML: https://mlsanity.com/paper/2105.11788/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2021.

## Built on by (most cited first, 1 of 1)

- [Bisimulation Learning](https://mlsanity.com/paper/2405.15723/) (2024)

## Abstract (arXiv)

The most efficient way to calculate strong bisimilarity is by calculation the relational coarsest partition on 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 |mathitAct|≤ m action labels, we provide an algorithm on max(n,m) processors that calculates strong bisimulation in time O(n+|mathitAct|) 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.