Abstract FR:

Le calcul de "pullback" a été introduit comme mécanisme de réécriture des graphes par M. Bauderon. Dans cette thèse, nous poursuivons cette approche, et nous étudions les réécritures des graphes dans le cadre des catégories au moyen du "pullback". A partir d'un "Pullback Lemma" classique dans la théorie des catégories, nous obtenons des résultats sur les diagrammes correspondants qui sont généralement valables pour toutes les catégories possédant des pullbacks. Ensuite nous passons dans les catégories de graphes. D'abord nous rappelons le vocabulaire du mécanisme de pullback, et puis en particulier, nous définissons les ingrédients permettant de construire la notion de grammaire de pullback. Avec les résultats sur les diagrammes, nous démontrons que cette classe de grammaires possède un caractère confluent et associatif au sens défini par B. Courcelle en 1987 (voir [Cou87]). Nous montrons aussi un exemple de grammaire qui engendre les grilles carrées. Nous explorons également une famille de graphes infinis construits à partir de ces grammaires. Nous démontrons que ces graphes sont automatiques et donc qu'ils ont une théorie du premier ordre décidable. Par contre la théorie du second-ordre monadique de ces graphes infinis n'est pas décidable en général.