ℤ-polyregular functions

This paper studies a robust class of functions from finite words to integers that we call Z-polyregular functions. We show that it admits natural characterizations in terms of logics, Z-rational expressions, Z-rational series and transducers.

We then study two subclass membership problems. First, we show that the asymptotic growth rate of a function is computable, and corresponds to the minimal number of variables required to represent it using logical formulas. Second, we show that firstorder definability of Z-polyregular functions is decidable. To show the latter, we introduce an original notion of residual transducer, and provide a semantic characterization based on aperiodicity. Formalism Characterization of ZPoly Characterization of ZSF Counting formulas Counting valuations in MSO (Definition II.5) Counting valuations in FO (Definition V.1) Polyregular functions sum • polyregular (Proposition II.13) sum • star-free polyregular (Proposition V.17) Z-rational expressions Closure of rational languages under Cauchy products, sums, and Z-products (Theorem II.20) Closure of star-free languages under Cauchy products, sums, and Z-products (Theorem V.4) Ultimately N -polynomial (Theorem II.31) Ultimately 1-polynomial (Theorem V.13) Z-rational series that are/have Polynomial growth (Theorem II.31) n/a Eigenvalues in 0 ∪ U (Theorem II.31) Eigenvalues in 0, 1 (Theorem V.18) Residual transducer Residual transducer (Corollary IV.19) Counter-free residual transducer (Theorem V.13)