Coinductive Characterisations Reveal Nice Relations Between Preorders and Equivalences

Abstract

There are two ways to define a semantics for process algebras: either directly by means of an equivalence relation or by means of a preorder whose kernel is the desired equivalence. We are interested in the relationship between these two presentations. Using our characterisation of the behaviour preorders by means of simulations up-to we were able to generate the canonical preorders corresponding to each behaviour equivalence. The axiomatizations of these preorders can be obtained by adding to the axioms of the equivalence that of the appropriate simulation. Aceto, Fokkink and Ingólfsdóttir have presented an algorithm that goes in the opposite direction, constructing an axiomatization of the induced equivalence from that of a given preorder. Following a different path we were able to get a correct proof and an enhanced algorithm. In this paper we present an shorter and simpler proof of this result, based on our coinductive characterisations of the behaviour preorders, and in particular in the existence of the canonical preorders. More important, we also present further generalisations of the result, since our coinductive characterisations are not only valid for the semantics coarser than the ready simulation.

By means of these new proofs and results we hope to contribute to a better knowledge of the semantics of processes and to better understand the tight relations between preorders and equivalences that define them.