This is a course on transducers, given before the Trends in Transformations workshop at FSTTCS 2019.
The course covers rational, regular and polyregular string-to-string functions. A special emphasis is made on theorems a la Krohn-Rhodes, which decompose complicated functions into simpler prime functions.
- Mealy machines, the classical Krohn-Rhodes theorem, and its corollaries for sequential and rational functions (slides).
- Regular functions, and some of their equivalent representations (two-way transducers, mso transductions, streaming string transducers, and regular list functions). The prime regular functions (slides).
- Polyregular functions, and some of their equivalent representations (pebble transducers, for transducers, functional programs, mso interpretations). The prime polyregular functions (slides).