L'algorithme de complétion de Knuth-Bendix permet, dans certains<br />cas, d'utiliser les systèmes de réécriture pour décider le<br />problème du mot dans un monoïde. Le problème du mot est alors<br />réduit a un calcul de forme normale. Cependant, tous les monoïdes<br />décidables ne peuvent pas être résolus de cette façon. Un<br />programme, initie par Squier, vise a caractériser par des<br />invariants algébriques la classe des monoïde décidables par<br />réécriture.<br />L'objectif de cette thèse est d'étendre ce travail a la réécriture<br />de termes.<br />Nous établissons des conditions de finitude homologique pour<br />l'existence de présentations convergentes de type fini par<br />réécriture de termes de théories équationnelles du premier ordre<br />avec une sorte. Une théorie équationnelle est sémantiquement<br />décrite par une théorie algébrique au sens de Lawvere. Nous<br />introduisons l'homologie de ces théories à coefficients dans les<br />bimodules non additifs, comme généralisation de l'homologie de<br />MacLane des anneaux. Cette homologie admet une interprétation en<br />terme d'homologie de Hochschild-Mitchell de la petite catégorie<br />sous-jacente. Nous généralisons les résolutions libres de Squier<br />et Kobayashi, établies en réécriture de mots, à la réécriture de<br />petites catégories. En utilisant ces résolutions, nous montrons<br />qu'une théorie algébrique admettant une présentation convergente<br />de type fini est de type bi-$\mathrm(PF)_(\infty)$. Nous<br />construisons une théorie équationnelle, non unaire, décidable et<br />n'admettant pas de présentation convergente de type fini.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00008784 |
| Date | 28 January 2004 |
| Creators | Malbos, Philippe |
| Publisher | Université Montpellier II - Sciences et Techniques du Languedoc |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0016 seconds