A coalgebraic perspective on linear weighted automata

dc.contributor.author Filippo Bonchi en
dc.contributor.author Alexandra Silva en
dc.contributor.author Jan Rutten en
dc.contributor.author Michele Boreale en
dc.contributor.author Marcello Bonsangue en
dc.date.accessioned 2017-11-16T14:09:38Z
dc.date.available 2017-11-16T14:09:38Z
dc.date.issued 2012 en
dc.description.abstract Weighted automata are a generalisation of non-deterministic automata where each transition, in addition to an input letter, has also a quantity expressing the weight (e.g. cost or probability) of its execution. As for non-deterministic automata, their behaviours can be expressed in terms of either (weighted) bisimilarity or (weighted) language equivalence. Coalgebras provide a categorical framework for the uniform study of state-based systems and their behaviours. In this work, we show that coalgebras can suitably model weighted automata in two different ways: coalgebras on SetSet (the category of sets and functions) characterise weighted bisimilarity, while coalgebras on VectVect (the category of vector spaces and linear maps) characterise weighted language equivalence. Relying on the second characterisation, we show three different procedures for computing weighted language equivalence. The first one consists in a generalisation of the usual partition refinement algorithm for ordi en
dc.identifier.uri http://repositorio.inesctec.pt/handle/123456789/2813
dc.identifier.uri http://dx.doi.org/10.1016/j.ic.2011.12.002 en
dc.language eng en
dc.relation 5610 en
dc.rights info:eu-repo/semantics/openAccess en
dc.title A coalgebraic perspective on linear weighted automata en
dc.type article en
dc.type Publication en
Files