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.