Trace Semantics via Determinization

Abstract : This paper takes a fresh look at the topic of trace semantics in the theory of coalgebras. The first development of coalgebraic trace semantics used final coalgebras in Kleisli categories, stemming from an initial algebra in the underlying category. This approach requires some non-trivial assumptions, like dcpo enrichment, which do not always hold, even in cases where one can reasonably speak of traces (like for weighted automata). More recently, it has been noticed that trace semantics can also arise by first performing a determinization construction. In this paper, we develop a systematic approach, in which the two approaches correspond to different orders of composing a functor and a monad, and accordingly, to different distributive laws. The relevant final coalgebra that gives rise to trace semantics does not live in a Kleisli category, but more generally, in a category of Eilenberg-Moore algebras. In order to exploit its finality, we identify an extension operation, that changes the state space of a coalgebra into a free algebra, which abstractly captures determinization of automata. Notably, we show that the two different views on trace semantics are equivalent, in the examples where both approaches are applicable.
Type de document :
Communication dans un congrès
Dirk Pattinson; Lutz Schröder. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. Springer, Lecture Notes in Computer Science, LNCS-7399, pp.109-129, 2012, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-642-32784-1_7〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01539887
Contributeur : Hal Ifip <>
Soumis le : jeudi 15 juin 2017 - 15:02:48
Dernière modification le : jeudi 15 juin 2017 - 15:25:48
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 12:09:46

Fichier

978-3-642-32784-1_7_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Bart Jacobs, Alexandra Silva, Ana Sokolova. Trace Semantics via Determinization. Dirk Pattinson; Lutz Schröder. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. Springer, Lecture Notes in Computer Science, LNCS-7399, pp.109-129, 2012, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-642-32784-1_7〉. 〈hal-01539887〉

Partager

Métriques

Consultations de la notice

106

Téléchargements de fichiers

38