A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

66 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
TitelFormal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings
RedacteurenGwen Salaün, Anton Wijs
UitgeverijSpringer
Pagina's115-133
Aantal pagina's19
ISBN van geprinte versie9783030906351
DOI's
StatusGepubliceerd - 2021
Evenement17th International Conference on Formal Aspects of Component Software, FACS 2021 - Virtual, Online
Duur: 28 okt. 202129 okt. 2021

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13077 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres17th International Conference on Formal Aspects of Component Software, FACS 2021
StadVirtual, Online
Periode28/10/2129/10/21

Bibliografische nota

Publisher Copyright:
© 2021, The Author(s).

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