Trace Semantics via Determinization - Coalgebraic Methods in Computer Science Access content directly
Conference Papers Year : 2012

Trace Semantics via Determinization


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.
Fichier principal
Vignette du fichier
978-3-642-32784-1_7_Chapter.pdf (371.88 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01539887 , version 1 (15-06-2017)





Bart Jacobs, Alexandra Silva, Ana Sokolova. Trace Semantics via Determinization. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. pp.109-129, ⟨10.1007/978-3-642-32784-1_7⟩. ⟨hal-01539887⟩
70 View
142 Download



Gmail Facebook X LinkedIn More