Prelegent: Mikołaj Bojańczyk

Polyregular functions are string-to-string functions that have polynomial size outputs. I will show that a polyregular function has growth rate O(n^k) if and only if it can be defined by an mso transduction of dimension k. On the other hand, the former two conditions are not equivalent to k-pebble automata; in fact there are polyregular functions of quadratic growth that require arbitrary numbers of pebbles to be computed.