1. Mikołaj Bojańczyk
   Polyregular Functions. CoRR, 2018   PDF

2. Mikołaj Bojańczyk, Sandra Kiefer, Nathan Lhote
   String-to-String Interpretations With Polynomial-Size Output. ICALP, 2019   PDF

Paper [1] (see also these slides) discusses a class of string-to-string functions, which goes beyond rational or regular functions, but still shares many of their good properties (e.g. the inverse image of a regular language is regular). This class is called the polyregular functions. Unlike the regular string-to-string functions (and their subclasses such as sequential or rational), which have linear size increase, the polyregular functions have polynomial size increase. The main selling point of the polyregular functions is that they admit numerous equivalent descriptions:

1. automata with pebbles (this definition comes from here and here);
2. a fragment of lambda calculus (this definition, as well as the other two below, is new to the author’s best knowledge);
3. a fragment of for-programs;
4. compositions of certain atomic functions, such as reverse or a form of string squaring.

Paper [2] adds another equivalent description to the list above, namely

5.  mso interpretations (which are like mso transductions, except that one output position is interpreted in a k-tuple of input positions.