On the Growth Rates of Polyregular Functions
Mikołaj Bojańczyk · 2023
We consider polyregular functions, which are certain string-to-string functions that have polynomial output size. We prove that a polyregular function has output size ${\mathcal{O}}({n^k})$ if and only if it can be defined by an MSO interpretation of dimension k, i.e. a string-to-string transformation where every output position is interpreted, using monadic second-order logic MSO, in some k-tuple of input positions. We also show that this characterization does not extend to pebble transducers, another model for describing polyregular functions: we show that for every {k ∈ 1, 2, …} there is a polyregular function of quadratic output size which needs at least k pebbles to be computed.