Trace semantics via generic observations

Sergey Goncharov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 -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.

Original languageEnglish
Title of host publicationAlgebra and Coalgebra in Computer Science - 5th International Conference, CALCO 2013, Proceedings
PublisherSpringer Verlag
Pages158-174
Number of pages17
ISBN (Print)9783642402050
DOIs
Publication statusPublished - 2013
Event5th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2013 - Warsaw, Poland
Duration: 3 Sept 20136 Sept 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8089 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2013
Country/TerritoryPoland
CityWarsaw
Period3/09/136/09/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Trace semantics via generic observations'. Together they form a unique fingerprint.

Cite this