Equations and Coequations for Weighted Automata

Abstract. We study weighted automata from both an algebraic and a coalgebraic perspective. In particular, we consider equations and coequa-tions for weighted automata. We prove a duality result that relates sets of equations (congruences) with (certain) subsets of coequations. As a consequence, we obtain two equivalent but complementary ways to de-fine classes of weighted automata. We show that this duality cannot be generalized to linear congruences in general but we obtain partial results when weights are from a field.