Abstract: String-to-string transducers generalize finite-state automata by having string outputs instead of merely booleans. There are already many classes of transducers studied in the literature such as Mealy machines, sequential functions, rational functions and regular functions.

All of the aforementioned classes contain only functions of linear growth, are closed under composition and reflect regular languages. They often admit several equivalent machine description: for instance, regular functions correspond to 2-way sequential transducers, MSO transductions, streaming string transducers, a suitable class of combinators and functions definable in the affine λ-calculus with linear Church encodings. Translating between those formalisms is not necessarily trivial.

The study of a nice class of transduction with polynomial-sized output garnered a lot of attention recently, starting with Bojańczyk who named them polyregular functions. A lot of nice equivalent characterizations of polyregular functions appeared in the literature since 2018.

In this talk, I will discuss a natural subclass of polyregular functions that Tito Nguyễn and I formally introduced to the literature in a 2021 paper. I will explain how it works using pebble transducers and a calculus of combinators and then give a sense of somewhat hard problems people look at in this space.