Abstract FR:

Le travail exposé dans cette thèse s'insère dans une théorie des automates infinis. Étant donnés un graphe orienté et étiqueté G et deux ensembles de sommets I, F de G, le langage des étiquettes de chemins de I à F est appelé <<trace>> dans G de I à F. On étudie deux transformations simples sur les graphes : la substitution finie inverse et le produit synchronisé par un graphe fini. Du point de vue logique ces transformations préservent la décidabilité de la théorie au second ordre monadique. Du point de vue des traces, on montre que ces transformations correspondent aux transductions rationnelles. Par analogie avec les <<Familles Abstraites de Langages>> (AFL) définie par Ginsburg et Greibach, on appelle <<Famille Abstraite de Graphes>> (AFG) une famille de graphes close par ces deux opérateurs. A toute famille de graphes correspond une famille de traces. Un parallèle est fait entre la théorie des familles de langages et celle des familles de graphes infinis : on montre que les traces des AFG sont des cônes rationnels. On montre aussi que les AFL (resp. Full-AFL) sont les traces des AFG (resp. Full-AFG) closes par union disjointe et ajout d'arc. On définie ensuite deux invariants pour les AFG : la <<finitude>> des degrés et la dimension au sens de Haussdorf. On étudie différentes familles de graphes du point de vue des AFG : les graphes préfixes, rationnels, synchrones et synchronisés (ou automatiques). On s'intéresse pour terminer à deux sous-AFG des graphes synchronisés~: les graphes congruentiels et affines définis par Conway. On montre notamment que le graphe de Collatz n'est structurellement pas préfixe.