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.CALCO.2015.35
URN: urn:nbn:de:0030-drops-55254
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5525/
Go to the corresponding LIPIcs Volume Portal

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

Towards Trace Metrics via Functor Lifting

pdf-format:
4.pdf (0.6 MB)

Abstract

We investigate the possibility of deriving metric trace semantics in a coalgebraic framework. First, we generalize a technique for systematically lifting functors from the category Set of sets to the category PMet of pseudometric spaces, by identifying conditions under which also natural transformations, monads and distributive laws can be lifted. By exploiting some recent work on an abstract determinization, these results enable the derivation of trace metrics starting from coalgebras in Set. More precisely, for a coalgebra in Set we determinize it, thus obtaining a coalgebra in the Eilenberg-Moore category of a monad. When the monad can be lifted to PMet, we can equip the final coalgebra with a behavioral distance. The trace distance between two states of the original coalgebra is the distance between their images in the determinized coalgebra through the unit of the monad. We show how our framework applies to nondeterministic automata and probabilistic automata.

BibTeX - Entry

@InProceedings{baldan_et_al:LIPIcs:2015:5525,
  author =	{Paolo Baldan and Filippo Bonchi and Henning Kerstan and Barbara K{\"o}nig},
  title =	{{Towards Trace Metrics via Functor Lifting}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{35--49},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Lawrence S. Moss and Pawel Sobocinski},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5525},
  URN =		{urn:nbn:de:0030-drops-55254},
  doi =		{10.4230/LIPIcs.CALCO.2015.35},
  annote =	{Keywords: trace metric, monad lifting, pseudometric, coalgebra}
}

Keywords: trace metric, monad lifting, pseudometric, coalgebra
Collection: 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)
Issue Date: 2015
Date of publication: 28.10.2015

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