Trace Semantics via Generic Observations

Conference contribution
(Conference Contribution)

Publication Details

Author(s): Goncharov S
Title edited volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher: Springer-verlag
Publishing place: Berlin/Heidelberg
Publication year: 2013
Title of series: Lecture Notes in Computer Science
Volume: 8089
Conference Proceedings Title: Proc. 5th Conference on Algebra and Coalgebra in Computer Science, CALCO 2013
Pages range: 158-174
ISBN: 978-3-642-40205-0
ISSN: 0302-9743


Recent progress on defining abstract trace semantics for coalgebras rests upon two observations: (i) coalgebraic bisimulation for deterministic automata coincides with trace equivalence, and (ii) the classical powerset construction for automata determinization instantiates the generic idea of lifting a functor to the Eilenberg-Moore category of an appropriate monad. We take this approach one step further by rebasing the latter kind of trace semantics on the novel notion of T-observer, which is just a certain natural transformation of the form F → GT, and thus allowing for elimination of assumptions about the structure of the coalgebra functor. As a specific application of this idea we demonstrate how it can be used for capturing trace semantics of push-down automata. Furthermore, we show how specific forms of observers can be used for coalgebra-based treatment of internal automata transitions as well as weak bisimilarity of processes.

FAU Authors / FAU Editors

Goncharov, Sergey Dr.-Ing.
Lehrstuhl für Informatik 8 (Theoretische Informatik)

How to cite

Goncharov, S. (2013). Trace Semantics via Generic Observations. In Proc. 5th Conference on Algebra and Coalgebra in Computer Science, CALCO 2013 (pp. 158-174). Berlin/Heidelberg: Springer-verlag.

Goncharov, Sergey. "Trace Semantics via Generic Observations." Proceedings of the 5th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2013, Warsaw Berlin/Heidelberg: Springer-verlag, 2013. 158-174.


Last updated on 2018-19-04 at 02:53