Elouan Renault
Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France
Weighted automata, introduced in 1961 by M. P. Schützenberger, generalize the automata, and increase their expressiveness. A weighted automaton depends on an alphabet and a semiring: an algebraic structure equipped with two operations satisfying some computational properties. Given a weighted automaton, a map from the set of words over this alphabet to this semiring can be defined, called the series of the weighted automaton.
Given two weighted automata, a natural question is whether they are equivalent, that is, if they realize the same series. Another interesting question is whether any of these weighted automata is minimal (in a sense to be specified).
As soon as weighted automata were introduced in 1961, M. P. Schützenberger answered these two questions in the affirmative for the case where the weighted automata are given over a semiring embeddable in a field, and even provided algorithms to test the equivalence of weighted automata and to compute a minimal weighted automaton. To do so, he used linear algebra techniques in a vector space on this field. Yet, these techniques can also be used in a module over division ring. Thanks to these techniques, these algorithmic results can be extended to the case when the semiring embeds in a division ring.
Among semirings, some of them play a central role: free semirings. Free structures are frequently studied. Free monoids, for instance, play a crucial role in automata theory. The only equalities satisfied by their elements are those implied by the axioms of a monoid. This lack of constraints grants them the status of natural representatives among monoids. Free semirings are to semirings what free monoids are to monoids. Since they are not commutative, these semirings cannot be embedded in a field. However, we will see that they can be embedded in a division ring.