Les structures automatiques (resp. arbre-automatiques) sont les structures relationnelles dont le domaine est un ensemble régulier de mots (resp. de termes) finis et dont chaque relation atomique est reconnaissable par un automate multi-bandes synchrones. Nous établissons des critères d'automaticité et énonçons des critères analogues d'arbre-automaticité, dont il découle en particulier, d'une part que le graphe aléatoire n'est pas automatique, ni même arbre-automatique, et d'autre part, que tout ordre bien fondé automatique est de hauteur strictement inférieure à  , et que   est l'ensemble des ordinaux arbre-automatiques. Pour citer cet article : C. Delhommé, C. R. Acad. Sci. Paris, Ser. I 339 (2004).

We establish criteria of automaticity and we state analogous criteria of tree-automaticity which show, on the one-hand that the random graph is neither automatic nor tree-automatic, and on the other hand that every well-founded automatic poset has height less than   and that   is the set of tree-automatic ordinals. To cite this article: C. Delhommé, C. R. Acad. Sci. Paris, Ser. I 339 (2004).