Une introduction à la réécriture de sommets dans les graphes
par produit fibré

Hélène Jacquet
(LaBRI, Bordeaux I)

Résumé J'indiquerai dans cet exposé comment la notion de produit fibré dans la catégorie des graphes (orientés, avec arcs multiples et boucles) et des morphismes de graphes permet de fournir un modèle apte à décrire la réécriture de sommets dans un graphe. La particularité de ce nouveau formalisme qui a été introduit par Michel Bauderon en 1995, réside d'une part dans le fait de définir l'étiquetage d'un graphe par l'intermédiaire d'un morphisme vers un graphe possédant une structure particulière - appelé graphe alphabet, et d'autre part de définir une règle de réécriture comme étant un morphisme vers ce même graphe alphabet. En résulte que l'application d'une règle à un graphe s'obtient ``automatiquement'' en effectuant le produit fibré de ces deux morphismes. J'indiquerai de quelle manière il est possible de montrer que tout langage engendré par une grammaire de l'approche dite ``ensembliste'' edNCE peut être engendré par une grammaire de produit fibré. Au delà des graphes, cette approche de la réécriture par produit fibré peut s'étendre uniformément au cadre de la réécriture dans les hypergraphes.

Mots-clefs : Graphe, Hypergraphe, Réécriture de graphes, Produit, Catégorie.