<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>27</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Filippo Bonchi</style></author><author><style face="normal" font="default" size="100%">Marcello Bonsangue</style></author><author><style face="normal" font="default" size="100%">Michele Boreale</style></author><author><style face="normal" font="default" size="100%">Jan Rutten</style></author><author><style face="normal" font="default" size="100%">Alexandra Silva</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">A coalgebraic perspective on linear weighted automata</style></title></titles><dates><year><style  face="normal" font="default" size="100%">2011</style></year><pub-dates><date><style  face="normal" font="default" size="100%">March</style></date></pub-dates></dates><urls><related-urls><url><style face="normal" font="default" size="100%">https://haslab.uminho.pt/sites/default/files/xana/files/18069a.pdf</style></url></related-urls></urls><number><style face="normal" font="default" size="100%">SEN 11-04</style></number><publisher><style face="normal" font="default" size="100%">Centrum Wiskunde &amp; Informatica (CWI)</style></publisher><pub-location><style face="normal" font="default" size="100%">Amsterdam, The Netherlands</style></pub-location><pages><style face="normal" font="default" size="100%">1-31</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">&lt;p&gt;Weighted automata are a generalization 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.&lt;/p&gt;
&lt;p&gt;Coalgebras provide a categorical framework for the uniform study of state-based systems and their behaviours.&lt;br /&gt;
In this work, we show that coalgebras can suitably model weighted automata in two different ways: coalgebras on Set (the category of sets and functions) characterize weighted bisimilarity, while coalgebras on Vect (the category of vector spaces and linear maps) characterize weighted language equivalence.&lt;/p&gt;
&lt;p&gt;Relying on the second characterization, we show three different procedures for computing weighted language equivalence. The first one consists in a generalization of the usual partition refinement algorithm for ordinary automata. The second one is the backward version of the first one. The third procedure relies on a syntactic representation of rational weighted languages.&lt;/p&gt;
</style></abstract></record></records></xml>