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

^*Corresponding author for this work

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

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
Subtitle of host publication	17th International Conference, FACS 2021, Virtual Event, October 28–29, 2021, Proceedings
Editors	Gwen Salaün, Anton Wijs
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	115-133
Number of pages	19
Volume	13077
ISBN (Electronic)	9783030906368
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).

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

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

Persistent URL (handle)

Persistent link

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, Virtual Event, October 28–29, 2021, Proceedings (Vol. 13077, pp. 115-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13077 LNCS). Springer Science and Business Media Deutschland GmbH. 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, Virtual Event, October 28–29, 2021, Proceedings. editor / Gwen Salaün ; Anton Wijs. Vol. 13077 Springer Science and Business Media Deutschland GmbH, 2021. pp. 115-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2d68948699ca4c6082443e313f87bf80,

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

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

volume = "13077",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "115--133",

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

booktitle = "Formal Aspects of Component Software",

address = "Germany",

}

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, Virtual Event, October 28–29, 2021, Proceedings. vol. 13077, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13077 LNCS, Springer Science and Business Media Deutschland GmbH, 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, Virtual Event, October 28–29, 2021, Proceedings. ed. / Gwen Salaün; Anton Wijs. Vol. 13077 Springer Science and Business Media Deutschland GmbH, 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.

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

UR - http://www.scopus.com/inward/citedby.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

AN - SCOPUS:85119829200

SN - 9783030906351

VL - 13077

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

A2 - Salaün, Gwen

A2 - Wijs, Anton

PB - Springer Science and Business Media Deutschland GmbH

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, Virtual Event, October 28–29, 2021, Proceedings. Vol. 13077. Springer Science and Business Media Deutschland GmbH. 2021. p. 115-133. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2021 Oct 28. 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

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this