Définissabilité dans certains réduits additifs d’anneaux euclidiens.

Description

Depuis les travaux de R. Büchi, on sait que les sous-ensembles reconnaissables de naturels (en base 2 par exemple) sont définissables dans certaines expansions de l’arithmétique de Presburger (et vice-versa), ce qui permet d’obtenir des résultats de décidabilité pour ces expansions. Par ailleurs, Cobham a montré qu’un sous-ensemble des nombres naturels qui est reconnaissable disons en base 2 et en base 3 est ultimement périodique (et donc définissable dans le groupe ordonné des entiers). M. Rigo et L. Waxweiler posent la question de savoir quel serait un analogue du théorème de Cobham dans les anneaux de polynômes sur un corps fini et montrent que la situation est plus complexe. Le point de départ de la thèse serait de reprendre le travail de Rigo et Waxweiler et de reposer le problème pour d’autres anneaux euclidiens pour lesquels, en collaboration avec Rigo et Waxweiler, nous avons obtenu des résultats analogues à ceux pour l’arithmétique de Presburger. Notons que récemment une nouvelle preuve du théorème de Cobham a été trouvée via la caractérisation de solutions simultanée à des équations linéaires de différence et différentielle.