Le séminaire LCR accueille Bruno Courcelle (Labri).

De manière à étendre aux graphes les concepts fondamentaux de la Théorie des Langages Formels, on définit sur l’ensemble des graphes finis deux structures d’algèbre (de "magma" selon une terminologie obsolète) qui généralisent la structure de monoïde libre. On en déduit de manière immédiate des notions de reconnaissabilité (par congruences finies) et d’algébricité (par systèmes d’équations à points fixes) pour les graphes , et de nombreuses propriétés prouvables au niveau algébrique.

L’expression de propriétés de graphes en Logique du Second-Ordre Monadique permet de concrétiser la notion d’ensemble reconnaissable de graphes, de même que les automates finis concrétisent celle de langage reconnaissable (de mots ou de termes). Cette logique permet aussi d’étendre la notion de transduction rationnelle et de famille génératrice pour les 2 types d’ensembles équationnels considérés.

Il en résulte de nombreux résultats en particulier : algorithmes FPT pour ces propriétés, le paramètre étant la largeur arborescente ou "de clique", théorèmes de filtrage pour les ensembles équationnels de graphes et résultats de décidabilité associés, constructions effectives des mineurs exclus.