(Bi)simulations up-to characterise process semantics

We define (bi)simulations up-to a preorder and show how we can use them to provide a coinductive, (bi)simulation-like, characterisation of semantic (equivalences) preorders for processes. In particular, we can apply our results to all the semantics in the linear time-branching time spectrum that are defined by preorders coarser than the ready simulation preorder. The relation between bisimulations up-to and simulations up-to allows us to find some new relations between the equivalences that define the semantics and the corresponding preorders. In particular, we have shown that the simulation up-to an equivalence relation is a canonical preorder whose kernel is the given equivalence relation. Since all of these canonical preorders are defined in an homogeneous way, we can prove properties for them in a generic way. As an illustrative example of this technique, we generate an axiomatic characterisation of each of these canonical preorders, that is obtained simply by adding a single axiom to the axiomatization of the original equivalence relation. Thus we provide an alternative axiomatization for any axiomatizable preorder in the linear time-branching time spectrum, whose correctness and completeness can be proved once and for all. Although we first prove, by induction, our results for finite processes, then we see, by using continuity arguments, that they are also valid for infinite (finitary) processes.

Authors

• David de Frutos Escrig
• Carlos Gregorio Rodríguez

Keywords

• Semantic equivalences
• Semantic preorders
• Bisimulations up-to
• Simulations up-to
• Canonical preorder
• Linear time-branching time spectrum