Revisiting the growth of polyregular functions: output languages, weighted automata and unary inputs
share
Polyregular functions are the class of string-to-string functions definable by pebble transducers (an extension of finite automata) or equivalently by MSO interpretations (a logical formalism). Their output length is bounded by a polynomial in the input length: a function computed by a k-pebble transducer or by a k-dimensional MSO interpretation has growth rate O(n^k). Bojańczyk has recently shown that the converse holds for MSO interpretations, but not for pebble transducers. We give significantly simplified proofs of those two results, extending the former to first-order interpretations by reduction to an elementary property of ℕ-weighted automata. For any k, we also prove the stronger statement that there is some quadratic polyregular function whose output language differs from that of any k-fold composition of macro tree transducers (and which therefore cannot be computed by any k-pebble transducer). In the special case of unary input alphabets, we show that k pebbles suffice to compute polyregular functions of growth O(n^k). This is obtained as a corollary of a basis of simple word sequences whose ultimately periodic combinations generate all polyregular functions with unary input. Finally, we study polyregular and polyblind functions between unary alphabets (i.e. integer sequences), as well as their first-order subclasses.
READ FULL TEXT