You are here

Weighted Bisimilarity in Linear (Co)Algebraic Form

18 June 2010
San Micheletto - Via S. Micheletto 3 (Classroom 3 )
Weighted automata are used to describe quantitative properties in various areas such as probabilistic systems, image compression and speech-to-text processing. The abstract behaviour of these automata is usually expressed in terms of weighted languages (also called formal power series), i.e., functions assigning to each word (in some alphabet) a weight (in some semiring). Another abstract behaviour can be expressed in terms of weighted bisimilarity that, differently from the weighted-language semantics, takes into account the full branching structure. In this talk, we show that (weighted) language semantics naturally arises from "linear coalgebras" on "vector spaces", while bisimilarity arises from "coalgebras" on "sets". These observations are also crucial for defining some algorithms for computing these semantics.