Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Milius, Stefan; Pattinson, Dirk; Schröder, Lutz http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-55389
URL:

; ;

Generic Trace Semantics and Graded Monads

pdf-format:


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
Seminar: 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)
Issue date: 2015
Date of publication: 2015


DROPS-Home | Fulltext Search | Imprint Published by LZI