Henning Kerstan
This website requires JavaScript. Please enable JavaScript for this website.

Coalgebraic Behavioral Metrics

published on Fri, 14 Sep 2018


We study different behavioral metrics, such as those arising from both branching and linear-time semantics, in a coalgebraic setting. Given a coalgebra for an endofunctor on Set, we define a framework for deriving pseudometrics on its carrier which measure the behavioral distance of states.

A crucial step is the lifting of the functor on Set to a functor on the category PMet of pseudometric spaces. We present two different approaches which can be viewed as generalizations of the Kantorovich and Wasserstein pseudometrics for probability measures. We show that the pseudometrics provided by the two approaches coincide on several natural examples, but in general they differ.

If the original functor has a final coalgebra, every lifting yields in a canonical way a behavioral distance which is usually branching-time, i.e., it generalizes bisimilarity. In order to model linear-time metrics (generalizing trace equivalences), we show sufficient conditions for lifting distributive laws and monads. These results enable us to employ the generalized powerset construction.