Behavioural Preorders via Graded Monads
share
Like notions of process equivalence, behavioural preorders on processes come in many flavours, ranging from fine-grained comparisons such as ready simulation to coarse-grained ones such as trace inclusion. Often, such behavioural preorders are characterized in terms of theory inclusion in dedicated characteristic logics; e.g. simulation is characterized by theory inclusion in the positive fragment of Hennessy-Milner logic. We introduce a unified semantic framework for behavioural preorders and their characteristic logics in which we parametrize the system type in the coalgebraic paradigm while behavioural preorders are captured as graded monads on the category Pos of partially ordered sets, in generalization of a previous approach to notions of process equivalence. We show the equivalence of graded monads on Pos with theories in a form of graded ordered algebra that we introduce here. Moreover, we provide a general notion of modal logic compatible with a given graded behavioural preorder, along with a criterion for expressiveness.
READ FULL TEXT