Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01539887
Contributor : Hal Ifip <>
Submitted on : Thursday, June 15, 2017 - 3:02:48 PM
Last modification on : Thursday, May 2, 2019 - 2:48:31 PM
Long-term archiving on: : Wednesday, December 13, 2017 - 12:09:46 PM

File

978-3-642-32784-1_7_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

216

Files downloads

380