Mikołaj Bojańczyk

Transducers and their Krohn-Rhodes decompositions


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.

  1. Mealy machines, the classical Krohn-Rhodes theorem, and its corollaries for sequential and rational functions (slides).
  2. 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).
  3. Polyregular functions, and some of their equivalent representations (pebble transducers, for transducers, functional programs, mso interpretations). The prime polyregular functions (slides).