Article in Edited Volumes
(Original article)

Simplified Coalgebraic Trace Equivalence

Publication Details
Author(s): Kurz A, Milius S, Pattinson D, Schröder L
Title edited volumes: Software, Services, and Systems
Publisher: Springer
Publishing place: Berlin
Publication year: 2015
Title of series: Lecture Notes in Computer Science
Volume: 8950
Pages range: 75-90
ISSN: 1611-3349


The analysis of concurrent and reactive systems is based to a large degree on various notions of process equivalence, ranging, on the so-called lineartime/ branching-time spectrum, from fine-grained equivalences such as strong bisimilarity to coarse-grained ones such as trace equivalence. The theory of concurrent systems at large has benefited from developments in coalgebra, which has enabled uniform definitions and results that provide a common umbrella for seemingly disparate system types including non-deterministic, weighted, probabilistic, and game-based systems. In particular, there has been some success in identifying a generic coalgebraic theory of bisimulation that matches known definitions in many concrete cases. The situation is currently somewhat less settled regarding trace equivalence. A number of coalgebraic approaches to trace equivalence have been proposed, none of which however cover all cases of interest; notably, all these approaches depend on explicit termination, which is not always imposed in standard systems, e.g. labelled transition systems. Here, we discuss a joint generalization of these approaches based on embedding functors modelling various aspects of the system, such as transition and braching, into a global monad; this approach appears to cover all cases considered previously and some additional ones, notably standard and probabilistic labelled transition systems.

How to cite
APA: Kurz, A., Milius, S., Pattinson, D., & Schröder, L. (2015). Simplified Coalgebraic Trace Equivalence. In Software, Services, and Systems (pp. 75-90). Berlin: Springer.

MLA: Kurz, Alexander, et al. "Simplified Coalgebraic Trace Equivalence." Software, Services, and Systems Berlin: Springer, 2015. 75-90.

BibTeX: Download
Share link
Last updated on 2017-09-23 at 02:43
PDF downloaded successfully