I will describe a class of string-to-string functions, called the polyregular functions.
The selling point of the polyregular functions is that they admit numerous equivalent descriptions:
(a) automata with pebbles;
(b) a fragment of lambda calculus;
(c) a fragment of for-programs;
(d) compositions of certain atomic functions, such as reverse or a form of string squaring; and
(e) string-to-string interpretations definable in monadic second-order logic.

Biografie

Mikołaj Bojańczyk did his PhD at the University of Warsaw (Poland) in 2004, where he is also now employed as a professor. He works on logic in computer science, with a special emphasis on connections between logic, automata and algebra. The general theme of his research is understanding how the notion of regularity extend beyond languages of finite words, by:
- studying objects other than words (e.g. trees, graphs, infinite objects etc.); - studying devices that have outputs beyond yes/no (e.g. transducers that output other objects).
Mikołaj Bojańczyk has received numerous awards such as the Ackerman Award (2006), the Presburger Award (2010), the Kuratowski Award (2007), the Lipski Prize (2006). He received the PODS Test of Time Award (2016) and the PODS Best Paper (2013 and 2006).