You are not logged in | Log in

We show that a polyregular word-to-word function is regular if and only its output size is at most linear in its input size.

Moreover a polyregular function can be realized by: a transducer with two pebbles if and only if its output

has quadratic size in its input, a transducer with three pebbles if and only if its output has cubic size in its input, etc.

Moreover the characterization is decidable and, given a polyregular function, one can compute a transducer realizing it

with the minimal number of pebbles. We apply the result to mso interpretations from words to words.

We show that mso interpretations of dimension $k$ exactly coincide with $k$-pebble transductions.

Pebble minimization for polyregular functions