Pebble Minimization of Polyregular Functions

Nathan Lhote

We show that a polyregular word-to-word function is regular if and only if its output size is at most linear in its input size. Moreover a polyregular function can be realized by:…