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

Milius, Stefan ; Pattinson, Dirk ; Schröder, Lutz

Generic Trace Semantics and Graded Monads

pdf-format:
18.pdf (0.5 MB)

Abstract

Models of concurrent systems employ a wide variety of semantics inducing various notions of process equivalence, ranging from linear-time semantics such as trace equivalence to branching-time semantics such as strong bisimilarity. Many of these generalize to system types beyond standard transition systems, featuring, for example, weighted, probabilistic, or game-based transitions; this motivates the search for suitable coalgebraic abstractions of process equivalence that cover these orthogonal dimensions of generality, i.e. are generic both in the system type and in the notion of system equivalence. In recent joint work with Kurz, we have proposed a parametrization of system equivalence over an embedding of the coalgebraic type functor into a monad. In the present paper, we refine this abstraction to use graded monads, which come with a notion of depth that corresponds, e.g., to trace length or bisimulation depth. We introduce a notion of graded algebras and show how they play the role of formulas in trace logics.

BibTeX - Entry

@InProceedings{milius_et_al:LIPIcs:2015:5538,
  author =	{Stefan Milius and Dirk Pattinson and Lutz Schr{\"o}der},
  title =	{{Generic Trace Semantics and Graded Monads}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{253--269},
  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/5538},
  URN =		{urn:nbn:de:0030-drops-55389},
  doi =		{10.4230/LIPIcs.CALCO.2015.253},
  annote =	{Keywords: transition systems, monads, coalgebra, trace logics}
}

Keywords: transition systems, monads, coalgebra, trace logics
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