Le jury est composé de :
Résumé :
La réécriture algébrique constitue un modèle de calcul adapté à une structure algébrique, consistant à orienter les relations de présentation de cette structure par générateurs et relations. Cette présentation orientée est appelée un système de réécriture. Cette approche permet de développer des méthodes de calcul ainsi que des méthodes constructives pour étudier ces structures. En particulier, elle permet de construire une famille génératrice de toutes les relations entre les relations, étendant ainsi une présentation convergente d’une structure algébrique en une présentation cohérente. Ces constructions s’appuient sur des résultats de réécriture comme le lemme de Newman, qui établit l’équivalence entre la confluence et la confluence locale dans les systèmes de réécriture terminants.
Dans cette thèse, nous étendons cette méthode de construction des présentations cohérentes au cas des systèmes de réécriture non-terminants. Pour cela, nous utilisons une variante du lemme de Newman développée par van Oostrom. Nous formulons nos résultats dans le langage polygraphique, qui catégorifie les systèmes de réécriture. Ainsi, nous étudions dans ce langage les systèmes abstraits de réécriture, les systèmes de réécriture de mots et les systèmes de réécriture dans les algèbres associatives.
Cette thèse s’organise en trois parties. Dans une première partie, nous établissons un résultat de cohérence pour les systèmes abstraits de réécriture non-terminants, en nous appuyant sur le principe d’induction par décroissance de van Oostrom. Dans une deuxième partie, nous appliquons ce résultat pour obtenir un résultat de cohérence pour les systèmes de réécriture de chemins dans les catégories, qui généralisent les systèmes de réécriture de mots. Dans ce cas, la preuve est également basée sur le principe d’induction par décroissance, en tenant compte de conditions liées à la stabilité de la décroissance par rapport aux contextes de réécriture, ainsi qu’à la décroissance des relations d’échange. Dans une troisième partie, nous établissons un théorème permettant de construire des présentations cohérentes à partir de présentations non-terminantes d’algèbres associatives. Pour ce faire, nous explicitons des hypothèses de stabilité de la décroissance par rapport aux contextes de la structure linéaire et de la décroissance des relations d’échange et des relations additives. Enfin, nous étendons cette approche à la construction des résolutions libres des algèbres associatives présentées par des systèmes de réécriture non-terminants.
