2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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. If you need more detail, I suggest looking at the book

Principles of Model Checking, Christel Baier and Joost-Pieter Katoen.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.