L'algèbre libre des termes syntaxiques construits à partir d'une signature donnée et d'un ensemble de variables : ses éléments sont des arbres de termes formels et les opérations sont les symboles de formation de termes ; elle satisfait la propriété universelle d'objet libre dans la catégorie des algèbres de cette signature.

Principe

Génération syntaxique et substitution : les termes se forment inductivement à partir de variables et de symboles de fonction, et la substitution/évaluation définit l'homomorphisme unique de l'algèbre de termes vers toute algèbre interprétant la signature.

Démonstration

Pour la signature avec un symbole binaire * et variables {x,y}, le terme *(x,*(y,x)) est un élément de l'algèbre de termes ; pour toute algèbre A interprétant *, toute affectation de x,y dans A induit un homomorphisme unique évaluant le terme en un élément de A.

Mauvaise application

Confondre l'algèbre de termes avec l'algèbre de toutes les fonctions sur un ensemble de variables ou avec un quotient de l'algèbre de termes par des équations non triviales ; l'algèbre de termes brute code la syntaxe pure, pas des identifications sémantiques sauf si l'on quotient.

Conséquence

Les algèbres de termes fournissent des modèles initiaux, fondent les algorithmes d'unification et d'appariement, et donnent des représentants syntaxiques pour les algèbres libres et pour la présentation de quotients implémentant des théories équationnelles.

Inversion

Un quotient de l'algèbre de termes par la plus petite congruence engendrée par un ensemble d'équations produit l'algèbre libre dans la théorie équationnelle correspondante ; le quotient efface des distinctions syntaxiques pour former des égalités sémantiques.

Limite

Les algèbres de termes pures n'imposent aucune identité au-delà de l'égalité syntaxique ; tout axiome imposé engendre des quotients — ainsi l'algèbre de termes n'appartient pas aux variétés définies par des identités non triviales tant que l'on n'a pas quotiented.

Tension sémantique

Entre syntaxe et sémantique : l'algèbre de termes est purement syntaxique et reflète les arbres de dérivation, alors que les algèbres sémantiques interprètent les symboles et peuvent identifier des termes distincts ; la réconciliation s'obtient par quotients via des théories équationnelles.

Synthèse

L'algèbre de termes est l'univers syntaxique des termes pour une signature qui, par sa propriété universelle de mappage, génère à la fois les algèbres libres et sert de source pour les quotients présentant des théories équationnelles et Horn ; elle est le pont de la syntaxe à la sémantique algébrique.