A linear parallel algorithm to compute bisimulation and relational coarsest partitions

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

13 Downloads (Pure)

Samenvatting

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 |Act|≤m action labels, we provide an algorithm on 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(nlogn) 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.
Originele taal-2Engels
Artikelnummer2105.11788
Aantal pagina's22
TijdschriftarXiv
Volume2021
StatusGepubliceerd - 2021

Vingerafdruk

Duik in de onderzoeksthema's van 'A linear parallel algorithm to compute bisimulation and relational coarsest partitions'. Samen vormen ze een unieke vingerafdruk.

Citeer dit