Weighted automata I

Weighted automata form an exciting field using methods from theoretical computer science, algebra, and combinatorics. They have recently received much interest due to their applications in digital image compression and in natural language processing. A weighted automaton consists of a finite number of states. Actions from an alphabet can induce a change of the current state into another one (a transition), and each transition carries a weight describing e.g. the ressources used for its execution, the length of time needed, its reliability, or an award associated with it. Thus a weighted automaton is simply a classical non-deterministic automaton with weights associated to the transitions. In our lectures, we will first describe how to define the behaviour of a weighted automaton. The weights are typically taken from a semiring, and the behaviour can often be described by suitable homomorphisms from the free monoid of all words over the alphabet of actions into a monoid of matrices over the given semiring - this is how algebra and combinatorics enter the scene. Then we will describe a fundamental characterization of the possible behaviours of weighted automata by rational formal power series, the Kleene-Schuetzenberger theorem. Afterwards, we will come to more recent research results on transformations of such behaviours and/or (depending on the time available) to descriptions of infinite behaviours of weighted automata. The lectures should be understandable to graduate students both of algebra and of computer science. No particular knowledge either of automata theory or of algebra is required.