Please use this identifier to cite or link to this item: http://repositorio.inesctec.pt/handle/123456789/2813
Title: A coalgebraic perspective on linear weighted automata
Authors: Filippo Bonchi
Alexandra Silva
Jan Rutten
Michele Boreale
Marcello Bonsangue
Issue Date: 2012
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
URI: http://repositorio.inesctec.pt/handle/123456789/2813
http://dx.doi.org/10.1016/j.ic.2011.12.002
metadata.dc.type: article
Publication
Appears in Collections:HASLab - Indexed Articles in Journals

Files in This Item:
File Description SizeFormat 
PS-08346.pdf623.61 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.