• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Critères de finitude homologique pour la non convergence des systèmes de réécriture de termes

Malbos, Philippe 28 January 2004 (has links) (PDF)
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.

Page generated in 0.1389 seconds