Trace Semantics for Coalgebras

Traditionally, traces are the sequences of labels associated with paths in transition systems X→P(A×X). Here we describe traces more generally, for coalgebras of the form X→P(F(X)), where F is a polynomial functor. The main result states that F's final coalgebra Z→≅F(Z) gives rise to a weakly final coalgebra with state space P(Z), in a suitable category of coalgebras. Weak finality means that there is a coalgebra map X→P(Z), but there is no uniqueness. We show that there is a canonical choice among these maps X→P(Z), namely the largest one, describing the traces in a suitably abstract formulation. A crucial technical ingredient in our construction is a general distributive law FP⇒PF, obtained via relation lifting.