Mikołaj Bojańczyk

Polyregular functions

October 22, 2018

This paper (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.



Leave a Reply

Your email address will not be published.