Simulation as Coarsest Partition Problem


The problem of determining the coarsest partition stable with respect to a given binary relation, is known to be equivalent to the problem of finding the maximal bisimulation on a given structure. Such an equivalence has suggested efficient algorithms for the computation of the maximal bisimulation relation. In this paper the simulation problem is rewritten in terms of coarsest stable partition problem allowing a more algebraic understanding of the simulation equivalence. On this ground, a new algorithm for deciding simulation is proposed. Such a procedure improves on either space or time complexity of previous simulation algorithms.

Proceedings of teh 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems,