Abstract FR:

L'addition de tout ordinal est connue pour etre decidable (par buchi, en 1965). L'algorithme de decision utilise des automates transfinis, et en etudiant sa complexite, on voit qu'elle est tres proche de la borne inferieure etablie par meyer (et amelioree par compton et henson). On etudie ensuite l'addition ordinale au moyen des jeux d'ehrenfeucht. On montre, par la methode de ferrante et rackoffle caractere borne de la structure des parties finies de n muni de l'inclusion et d'une relation d'ordre partiel. La puissance generalisee est l'outil qui permet, par iteration, de transmettre ce caractere borne a l'addition de tout ordinal strictement inferieur a ##. On voit enfin que la structure multiplicative des entiers naturels reste decidable, lorsqu'on ajoute au langage la restriction de l'ordre a l'ensemble des nombres premiers