Tanguy Urvoy - 16 juin 2003
Familles abstraites de graphes
http://www.irisa.fr/bibli/publi/theses/2003/urvoy/urvoy.html
Thesis submitted to IFSIC

Résumé
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éfinies
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éfinit ensuite deux invariants pour les AFG: la <<finitude>> des degrés
et la dimension au sens de Hausdorff. 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.

Mots clefs: Informatique théorique, théorie des langages, théorie des
automates, familles de langages, familles abstraites

Abstract
This work takes place in an infinite automata theory. Given an edge
labeled transition graph G, and two sets of vertices I, F of G, the path
language from I to F is called the "trace" of G from I to F. We study
two simple transformations on graphs: the finite inverse substitution
and the synchronized product with a finite graph. From logical point of
view, these transformations preserve decidability of monadic second
order logic. From traces point of view, we show that these
transformations are equivalent to rational transductions. By analogy
with the "Abstract Families of Languages" (AFL) defined by Ginsburg and
Greibach, we call "Abstract Family of Graphs" (AFG) a graph family that
is closed by these two operators. We show that AFL (resp. full-AFL) are
the traces of AFG (resp. full-AFG) that are closed by disjoint union and
finite arc addition. We then define two invariants for AFG: the
"finiteness" of degrees and the Hausdorff dimension. We study different
families of graphs through AFG: prefix graphs, prefix recognizable
graphs, rational and automatic graphs. We focus on two sub-AFG of
automatic graphs: the congruential and "linear" graphs defined by
Conway. We show that the Collatz graph is structurally not prefix.

Keywords: Theoretical computer science, languages theory, automata
theory, families of languages, abstract families