19th Estonian Winter School in Computer Science (EWSCS)
XIX Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 2 - 7, 2014

Jacques Sakarovitch

CNRS / Télécom Paristech
France

An introduction to weighted automata theory

Abstract

In the last 15 years, quantitative models and quantitative analysis have become of common usage in many areas of computer science, from software verification to natural language processing for instance. Classical models of computation where sequences are either accepted or not, are replaced by models where sequences are associated with values, be it probabilities, or costs, or outputs, in order to get more detailed or useful information on the computations.

Finite automata is the simplest model of computation, the strongest restriction imposed upon Turing machines. Finite automata with weights is also the simplest computation model that incorporates multiplicities. But the variety of possible weights makes the subject wide open and rich of many developments.

In these lectures, and after the description of the model, some results and problems from weighted automata theory are presented with a unifying point of view that is more common to classical control theory: how can a given automaton - a system - be transformed in order to comply with certain constraints without changing its behaviour. Three main problems will be tackled along this line: reduction, contraction, sequentialisation.

Reduction is the problem of finding an equivalent automaton of smaller size, hopefully of minimal size. Contraction addresses the same problem with the constraint of keeping the structure of the computations. It amounts to the definition of morphisms for weighted automata and proves to be equivalent to the notion of simulation developed in other contexts. Sequentialisation is the problem of realisability of a weighted automaton by a deterministic process. Whether it is decidable if the behaviour of a weighted automaton may be realised by a sequential one is a question whose solution depends upon the weight semiring. The main classical cases will be considered, some being decidable, some undecidable, and some still open.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed May 21, 2016 23:38 EET by local organizers, ewscs14(at)cs.ioc.ee
EWSCS'14 page: http://cs.ioc.ee/ewscs/2014/