Generic Trace Semantics and Graded Monads

Milius S, Pattinson D, Schröder L (2015)

Publication Type: Conference contribution, Original article

Publication year: 2015

Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

City/Town: Dagstuhl

Pages Range: 253--269

Conference Proceedings Title: 6th Conference on Algebra and Coalgebra in Computer Science, CALCO 2015

Event location: Nijmegen

DOI: 10.4230/LIPIcs.CALCO.2015.253

Open Access Link: http://drops.dagstuhl.de/opus/volltexte/2015/5538/pdf/18.pdf

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.
 

Authors with CRIS profile

Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik) Lutz Schröder Lehrstuhl für Informatik 8 (Theoretische Informatik)

Related research project(s)

Coinduction Meets Algebra For the Axiomatization of System Equivalence (COAX) Oct. 1, 2014 - July 31, 2018 Probabilistische Beschreibungslogik als Fragment der Probabilistischen Logik Erster Stufe (ProbDL) April 1, 2011 - April 1, 2014

Involved external institutions

Australian National University (ANU) AU Australia (AU)

How to cite

APA:

Milius, S., Pattinson, D., & Schröder, L. (2015). Generic Trace Semantics and Graded Monads. In 6th Conference on Algebra and Coalgebra in Computer Science, CALCO 2015 (pp. 253--269). Nijmegen: Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

MLA:

Milius, Stefan, Dirk Pattinson, and Lutz Schröder. "Generic Trace Semantics and Graded Monads." Proceedings of the 6th Conference on Algebra and Coalgebra in Computer Science, Nijmegen Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. 253--269.

BibTeX: Download