A tutorial on sequential functions: I - Minimization of sequential transducers; II - Composition, the wreath product principle and its applications

The first part of this tutorial will just require a basic knowledge on finite deterministic automata. The second part will be more advanced, but all necessary background will be recalled.

Sequential functions are, in the sense, the simplest computable functions. There are especially interesting for hardware designers, since they are easily implemented on circuits. In the first part, I will recall the definition of sequential automata, present several examples (addition, cut and replace, division by a fixed integer, coding, etc.) and explain the little known minimisation algorithm. I will also state, without proof, a nice characterization of these functions. The second part will be devoted to the composition of sequential functions. I will show in particular that certain operations on languages (notably the concatenation product) and the operators of linear temporal logic, can be expressed in terms of sequential functions. I will explain how to use this interpretation to characterize various classes of languages or obtain decidability results.  

hosted by