Talk "Simple Coalgebraic Traces for Coalgebras of Composed Monads"

by Ana Sokolova

Tue, 25 April 2023 at 03:20 pm in Paris, France

Joint work with: Daniela Petrisan

Abstract: We study coalgebraic trace semantics for coalgebras of composite monads, focusing on a simple definition of the semantics where traces after a finite number of steps are obtained by iterating the Kleisli extension, also known as determinisation, of the coalgebra structure and observing in an algebra of observations. Despite its simplicity this approach to trace semantics is known to cover the more elaborate notions for coalgebras of a monad. Monads compose via strong and weak distributive laws. Recent results on this topic, by Cheng and by Goy and Petrisan, enable iterative composition of multiple monads, which we exploit in this paper: We show how traces of composed monads relate to traces of "partial determinisations" for the constitutive parts. As a running example we consider transition systems with probabilities, non-determinism, and action labels which are coalgebras of a monad obtained by composing multiple monads, and show e.g. that non-deterministic traces of the belief-state transformer -- studied for distribution bisimilarity by Bonchi, Silva, and Sokolova -- coincide with traces of the original system. Our results yield a method for iterative (nested) notions of semantics.