Generic Trace Semantics and Graded Monads

Conference contribution
(Original article)


Publication Details

Author(s): Milius S, Pattinson D, Schröder L
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publishing place: Dagstuhl
Publication year: 2015
Conference Proceedings Title: 6th Conference on Algebra and Coalgebra in Computer Science, CALCO 2015
Pages range: 253--269


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.

 



FAU Authors / FAU Editors

Milius, Stefan apl. Prof. Dr.
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Schröder, Lutz Prof. Dr.
Lehrstuhl für Informatik 8 (Theoretische Informatik)


External institutions with authors

Australian National University (ANU)


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: 

Last updated on 2018-12-12 at 13:50