In this paper we define simulations up-to a preorder and show how we can use them to provide a coinductive, simulation-like, characterization of semantic preorders for processes. The result applies to a wide class of preorders, in particular to all semantic preorders coarser than the ready simulation preorder in the linear time-branching time spectrum. An interesting but unexpected result is that, when built from an equivalence relation, the simulation up-to is a canonical preorder whose kernel is the given equivalence relation. These canonical preorders have several nice properties, the main being that since all of them are defined in a homogeneous way, their properties can be proved in a generic way. In particular, we present an axiomatic characterization of each of these canonical preorders, that is obtained just by adding a single axiom to the axiomatization of the original equivalence relation. This gives us an alternative axiomatization for every axiomatizable preorder in the linear time-branching time spectrum, whose correctness and completeness can be proved once and for all.
-Unlike Theorem 5.1 of REF , our main result applies to all of the semantics in the spectrum whose discriminating power lies in between that of ready simulation semantics and partial traces semantics.
Simulations up-to and Canonical Preorders (extended abstract) Abstract
Electron. Notes Theor. Comput. Sci.
Electron. Notes Theor. Comput. Sci.
Computer Science