Name
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(n log 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-90636-8_7 | FORMAL ASPECTS OF COMPONENT SOFTWARE (FACS 2021) |
DocType | Volume | ISSN |
Conference | 13077 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jan Martens | 1 | 0 | 0.34 |
| Jan Friso Groote | 2 | 0 | 0.34 |
| Lars van den Haak | 3 | 0 | 0.34 |
| Pieter Hijma | 4 | 0 | 0.34 |
| Anton Wijs | 5 | 203 | 22.84 |