Abstract FR:

Le présent mémoire est dédié à l'étude des propriétés de définissabilité et, plus particulièrement, à la description des ensembles définissables dans de structures logiques qui s'interprètent naturellement dans la théorie des automates et à l'étude d'un problème de définissabilité de sous-structures. La thèse est divisée en deux parties principales : la première relative à l'étude de structures ayant pour domaine l'ensemble des entiers relatifs (et donc reliée aux langages sur des mots finis), la deuxième relative à l'étude de structures ayant pour domaine l'ensemble des entiers p-adiques (et donc reliée aux langages sur des mots infinis). La première partie étudie l'arithmétique de Presburger, c'est-à-dire l'arithmétique des entiers sans la multiplication. En donnant une caractérisation des ensembles définissable dans arithmétique faible de Presburger, nous prouvons la décidabilité de l'arithmétique faible de Presburger dans l'arithmétique de Presburger. La seconde partie de notre travail est par contre dédiée aux automates qui reconnaissent des mots infinis vus comme le codage de structures des donnes pour la manipulation de nombres. Contrairement à l'approche habituelle, nous considérerons les mots infinis comme le codage d'un entier p-adique. Nous prouverons que les ensembles d'entiers p- adiques reconnus par un automate de Buchi sont ceux exprimables au premier ordre dans une particulaire structure. Nous étudierons en outre la puissance expressive de quelques sous- structures, en établissant, quand cela est possible, une élimination des quantificateurs.