A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions

Jan Martens; Jan Friso Groote; Lars van den Haak; Pieter Hijma; Anton Wijs

doi:10.1007/978-3-030-90636-8_7

A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions

Jan Martens, Jan Friso Groote, Lars van den Haak, Pieter Hijma, Anton Wijs

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

197 Downloads (Pure)

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.

Original language	English
Title of host publication	Formal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings
Editors	Gwen Salaün, Anton Wijs
Publisher	Springer
Pages	115-133
Number of pages	19
ISBN (Print)	9783030906351
DOIs	https://doi.org/10.1007/978-3-030-90636-8_7
Publication status	Published - 2021
Event	17th International Conference on Formal Aspects of Component Software, FACS 2021 - Virtual, Online Duration: 28 Oct 2021 → 29 Oct 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13077 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Conference on Formal Aspects of Component Software, FACS 2021
City	Virtual, Online
Period	28/10/21 → 29/10/21

Bibliographical note

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

Keywords

Bisimulation
Relational Coarsest Partition

Access to Document

10.1007/978-3-030-90636-8_7

2105.11788Submitted manuscript, 465 KB

https://arxiv.org/abs/2105.11788

Cite this

Martens, J., Groote, J. F., van den Haak, L., Hijma, P., & Wijs, A. (2021). A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions. In G. Salaün, & A. Wijs (Eds.), Formal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings (pp. 115-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13077 LNCS). Springer. https://doi.org/10.1007/978-3-030-90636-8_7

Martens, Jan ; Groote, Jan Friso ; van den Haak, Lars et al. / A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions. Formal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings. editor / Gwen Salaün ; Anton Wijs. Springer, 2021. pp. 115-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s).; 17th International Conference on Formal Aspects of Component Software, FACS 2021 ; Conference date: 28-10-2021 Through 29-10-2021",

year = "2021",

doi = "10.1007/978-3-030-90636-8_7",

language = "English",

isbn = "9783030906351",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "115--133",

editor = "Gwen Sala{\"u}n and Anton Wijs",

booktitle = "Formal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings",

}

Martens, J , Groote, JF , van den Haak, L, Hijma, P & Wijs, A 2021, A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions. in G Salaün & A Wijs (eds), Formal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13077 LNCS, Springer, pp. 115-133, 17th International Conference on Formal Aspects of Component Software, FACS 2021, Virtual, Online, 28/10/21. https://doi.org/10.1007/978-3-030-90636-8_7

A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions. / Martens, Jan ; Groote, Jan Friso ; van den Haak, Lars et al.
Formal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings. ed. / Gwen Salaün; Anton Wijs. Springer, 2021. p. 115-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13077 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions

AU - Martens, Jan

AU - Groote, Jan Friso

AU - van den Haak, Lars

AU - Hijma, Pieter

AU - Wijs, Anton

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Bisimulation

KW - Relational Coarsest Partition

UR - http://www.scopus.com/inward/record.url?scp=85119829200&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-90636-8_7

DO - 10.1007/978-3-030-90636-8_7

M3 - Conference contribution

SN - 9783030906351

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 115

EP - 133

BT - Formal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings

A2 - Salaün, Gwen

A2 - Wijs, Anton

PB - Springer

T2 - 17th International Conference on Formal Aspects of Component Software, FACS 2021

Y2 - 28 October 2021 through 29 October 2021

ER -

Martens J , Groote JF , van den Haak L, Hijma P, Wijs A. A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions. In Salaün G, Wijs A, editors, Formal Aspects of Component Software - 17th International Conference, FACS 2021, Proceedings. Springer. 2021. p. 115-133. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-90636-8_7

A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this