A Coalgebraic Perspective on Linear Weighted Automata

Filippo Bonchi (1) , Marcello Bonsangue (2) , Michele Boreale (3) , Jan Rutten (2) , Alexandra Silva (2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 CWI - Centrum voor Wiskunde en Informatica
3 DSI - Dipartimento di Sistemi e Informatica

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. Coalgebras provide a categorical framework for the uniform study of tate-based systems and their behaviours. 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. Relying on the second characterization, we show three different procedures for computing weighted language equivalence. The first one consists in a generalizion 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.

Mots clés: Coalgebras; Weighted Automata; Formal Power Series; Minimization Algorithm

Domaines: Logique en informatique [cs.LO]

Filippo Bonchi, Marcello Bonsangue, Michele Boreale, Jan Rutten, Alexandra Silva. A Coalgebraic Perspective on Linear Weighted Automata. Information and Computation, 2012, 211, pp.77-105. ⟨hal-00576921⟩