Return to search

Présentations d'opérades et systèmes de réécriture

Cette thèse étudie les propriétés calculatoires des présentations d'opérades, ou systèmes de réécriture de diagrammes de Penrose, et leurs liens avec divers types de systèmes de réécriture classiques. Grâce à des nouveaux critères pour la terminaison et la confluence, on démontre la conjecture sur la convergence de la présentation L(Z2) des Z/2Z-espaces vectoriels, une théorie équationnelle commutative. On montre que les présentations d'opérades sont des généralisations des systèmes de réécriture de mots et des réseaux de Petri et qu'elles fournissent un calcul de gestion explicite des ressources pour les systèmes de réécriture de termes linéaires à gauche. Enfin, on étudie les obstructions à ce même résultat concernant le lambda-calcul. Des annexes présentent les liens entre les opérades et d'autres structures de l'algèbre universelle, ainsi qu'un calcul de substitutions explicites.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00006863
Date28 June 2004
CreatorsGuiraud, Yves
PublisherUniversité Montpellier II - Sciences et Techniques du Languedoc
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0017 seconds