License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.403
URN: urn:nbn:de:0030-drops-48599
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4859/
Go to the corresponding LIPIcs Volume Portal

Baldan, Paolo ; Bonchi, Filippo ; Kerstan, Henning ; König, Barbara

Behavioral Metrics via Functor Lifting

pdf-format:
35.pdf (0.5 MB)

Abstract

We study behavioral metrics in an abstract coalgebraic setting. Given a coalgebra alpha : X -> FX in Set, where the functor F specifies the branching type, we define a framework for deriving pseudometrics on X which measure the behavioral distance of states.

A first crucial step is the lifting of the functor F on Set to a functor /F in 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.

Then a final coalgebra for F in Set can be endowed with a behavioral distance resulting as the smallest solution of a fixed-point equation, yielding the final /F-coalgebra in PMet. The same technique, applied to an arbitrary coalgebra alpha : X -> FX in Set, provides the behavioral distance on X. Under some constraints we can prove that two states are at distance 0 if and only if they are behaviorally equivalent.

BibTeX - Entry

@InProceedings{baldan_et_al:LIPIcs:2014:4859,
  author =	{Paolo Baldan and Filippo Bonchi and Henning Kerstan and Barbara K{\"o}nig},
  title =	{{Behavioral Metrics via Functor Lifting}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{403--415},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4859},
  URN =		{urn:nbn:de:0030-drops-48599},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.403},
  annote =	{Keywords: behavioral metric, functor lifting, pseudometric, coalgebra}
}

Keywords: behavioral metric, functor lifting, pseudometric, coalgebra
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI