Definability in certain additive reducts of Euclidean rings.

Description

It is now well-known that recognizable subsets of natural numbers, say in base 2, are definable in certain expansions of Presburger arithmetic (and conversely). This allows to obtain decidability results for these expansions. A natural question to ask is which properties of the natural numbers (or the integers) make these results work ? With M. Rigo and L. Waxweiler, we generalize the set-up to some euclidean rings, following their former work on polynomial rings over finite fields. In their paper, they also ask the question of finding an analog of the theorem of Cobham on the subsets on natural numbers which are recognizable say in basis 2 and 3. They show that the situation in polynomial rings is more complex . The thesis project would be first to revisit their work and then possibly to enlarge it to other euclidean rings. Note that a new proof of Cobham’s theorem has been recently found through the study of simultaneous solutions of linear difference and differential equations.