A distributed algorithm for strong bisimulation reduction of state spaces

S.C.C. Blom, S.M. Orzan

Research output: Contribution to journalArticleAcademicpeer-review

41 Citations (Scopus)
1 Downloads (Pure)


It is a known problem that state spaces can grow very large, which makes operating on them (including reducing them) difficult because of operational memory shortage. In an attempt to extend the size of the state spaces that can be dealt with, we designed and implemented a bisimulation reduction algorithm for distributed memory settings using message passing communication. By using message passing, the same implementation can be used on both clusters of workstations and large shared memory machines. The algorithm performs reduction of large labeled transition systems modulo strong bisimulation. We justify its correctness and termination and provide an evaluation of the worst-case time and message complexity and some performance data from a prototype implementation. Both theory and practice show that the algorithm scales up with the number of workstations.
Original languageEnglish
Pages (from-to)74-86
JournalInternational Journal on Software Tools for Technology Transfer
Issue number1
Publication statusPublished - 2005


Dive into the research topics of 'A distributed algorithm for strong bisimulation reduction of state spaces'. Together they form a unique fingerprint.

Cite this