Trace Semantics via Generic Observations
Author(s): Goncharov S
Title edited volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publishing place: Berlin/Heidelberg
Publication year: 2013
Title of series: Lecture Notes in Computer Science
Conference Proceedings Title: Proc. 5th Conference on Algebra and Coalgebra in Computer Science, CALCO 2013
Pages range: 158-174
Event: 5th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2013
Event location: Warsaw
Start date of the event: 03/09/2013
End date of the event: 06/09/2013
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 How to cite
APA: 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.
MLA: 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.