[en] Numeration System ; Finite field ; Polynomial ; Presburger arithmetic ; Logical characterization ; Decidable theory

[en] The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination of powers of a non-constant polynomial P playing the role of the base of the numeration. Having in mind the theorem of Cobham from 1969 about recognizable sets of integers, it is natural to study $P$-recognizable sets of polynomials. Based on the results obtained in the Ph.D. thesis of the second author, we study the logical characterization of such sets and related properties like decidability of the corresponding first-order theory.

Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination of powers of a non-constant polynomial P seen as a base of numeration. We study P-recognizable sets of polynomials, i.e., sets whose language of representations in base P is regular, their logical characterization and related properties like decidability of the corresponding first-order theory.