<p>The coarsest bisimulation has a well known greatest fixed point characterisation. This greatest fixed point characterisation gives you a simple algorithm to calculate bisimulation quotients. There are quite a few immediate improvements you can make to this algorithm. A reference that contains most of these details is <a href="http://www-i2.informatik.rwth-aachen.de/i2/fileadmin/user_upload/documents/AMC09/amc09_lec2.pdf" rel="nofollow">Joost Pieter Katoen's lecture on bisimulation minimization</a>. If you need more detail, I suggest looking at the book</p>

<blockquote>
  <p><a href="http://rads.stackoverflow.com/amzn/click/026202649X" rel="nofollow">Principles of Model Checking</a>, Christel Baier and Joost-Pieter Katoen.</p>
</blockquote>

CC BY-SA 3.0
2013-09-17T20:47:53.400Z
2013-09-17T20:47:53.400Z
Vijay D
<p>Is there a simple algorithm to calculate the maximal bisimulation relation of a graph/two graphs?
With simple i mean very easy implementation, complexity is not that important for us in this stage.</p>

<graph-theory><graph-algorithms>
Simple Bisimulation algorithm
Jonny5
# Simple Bisimulation algorithm

(Asked by: username_0 on 2013-09-17)

Is there a simple algorithm to calculate the maximal bisimulation relation of a graph/two graphs?
With simple i mean very easy implementation, complexity is not that important for us in this stage.

**Tags:** graph-theory, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2013-09-17. Score: 2 | Accepted answer

The coarsest bisimulation has a well known greatest fixed point characterisation. This greatest fixed point characterisation gives you a simple algorithm to calculate bisimulation quotients. There are quite a few immediate improvements you can make to this algorithm. A reference that contains most of these details is [Joost Pieter Katoen's lecture on bisimulation minimization](http://www-i2.informatik.rwth-aachen.de/i2/fileadmin/user_upload/documents/AMC09/amc09_lec2.pdf). If you need more detail, I suggest looking at the book

> [Principles of Model Checking](http://rads.stackoverflow.com/amzn/click/026202649X), Christel Baier and Joost-Pieter Katoen.


---

