Terme (logique)

Un terme est une expression de base du calcul des prédicats, de l'algèbre, notamment de l'algèbre universelle, et du calcul formel, des systèmes de réécriture et de l'unification. C'est l'objet produit par une analyse syntaxique. Sa principale caractéristique est d'être homogène (il n'y a que des opérations de base et pas d'opérations logiques) et de décrire l'agencement des opérations de base. Un terme est parfois appelé une formule du premier ordre. Par exemple, (x + f(x,y)) * 3 et *(+(x,f(x,y)),3) et *+xfxy3 et la figure à droite représentent le même terme sous quatre formes externes différentes.

Description

À la base des termes, il y a des opérateurs qui sont répartis dans une signature. Les opérateurs sont les symboles de base, tandis que la signature attribue une arité à chaque opérateur. L'arité est le nombre d'arguments qu'attend un opérateur. Ainsi il y aura des opérateurs unaires (d'arité 1), des opérateurs binaires (d'arité 2), des opérateurs ternaires (d'arité 3) et plus généralement des opérateurs $n$ -aires. Les opérateurs 0-aires sont ceux qui n'attendent pas d'arguments et sont appelés des constantes. Dans le cas où on désire des termes avec des variables on ajoute à l'ensemble $\Sigma _{0}$ un ensemble dénombrable $X$ dit ensemble des variables. Plus formellement une signature est définie ainsi :

\mathbf {\Sigma } =\bigcup _{i=0}^{\infty }\Sigma _{i}

,

où $\Sigma _{i}$ est l'ensemble des opérateurs $i$ -aires. Par exemple, dans les groupes, la signature comporte trois ensembles non vides d'opérateurs $\Sigma _{0}=\{e\}$ , $\Sigma _{1}=\{\_^{-1}\}$ et $\Sigma _{2}=\{\bullet \}$ . Autrement dit, dans les groupes il y a une constante $e$ , un opérateur unaire qui s'écrit $a^{-1}$ (notation suffixe) quand il est appliqué à un élément $a$ et un opérateur binaire qui s'écrit (notation infixe) $a\bullet b$ quand il est appliqué à $a$ et $b$ . Notons cependant que la plupart du temps les termes sont écrits en notation préfixée, c'est-à-dire sous la forme $f(a_{1},...,a_{n})$ , par exemple $f(a_{1},a_{2},a_{3})$ pour un opérateur ternaire. Notons aussi que si l'arité est bien spécifiée, on peut se passer des parenthèses dans une notation dite notation polonaise ou notation de Łukasiewicz

Il y a différentes définitions des termes qui sont équivalentes.

Définition récursive

On peut définir récursivement l'ensemble $T$ des termes ainsi

T=\bigcup _{i=0}^{\infty }\bigcup _{f\in \Sigma _{i}}f(T,...i~fois...,T)

Définition comme application d'un ensemble de positions vers une signature

La définition utilisant la notion d'ensemble de positions d'un terme permet de décrire facilement différentes propriétés et différents algorithmes sur les termes.

Un ensemble ${\mathit {P}}$ de mots sur l'ensemble des entiers positifs est un ensemble de positions si

${\mathit {P}}$ est fini et non vide,
$p\in {\mathit {P}}$ et $q$ préfixe de $p$ impliquent $q\in {\mathit {P}}$ ,
$pi\in {\mathit {P}}$ et $j\in \mathbb {N} -\{0\}$ et $j<i$ impliquent $pj\in {\mathit {P}}$ .

Un terme $s$ est une application d'un ensemble ${\mathit {P}}$ de positions dans une signature avec la contrainte que si $s(p)=f\in \Sigma _{n}$ alors $pi\in {\mathit {P}}$ si et seulement si $i\leq n$ . ${\mathit {P}}$ est alors appelé l'ensemble des positions du terme $s$ et noté ${\mathit {Pos}}(s)$ .

La propriété 2. ci-dessus signifie que si $p$ est une position d'un terme, alors toute position préfixe est aussi une position dans le terme (située au-dessus). La propriété 3. ci-dessus signifie que si $p$ est une position d'un terme, alors toute position située sous le même symbole mais à sa gauche est aussi une position dans le terme. La contrainte ajoutée dit que si un nœud est étiqueté par un symbole d'arité $n$ alors il a exactement $n$ fils.

Définition en tant qu'arbre étiqueté orienté

Représentation arborescente des termes (n*(n+1))/2 et n*((n+1)/2)

Un terme peut être vu comme un arbre^[1] étiqueté (à chaque nœud est associé une étiquette prise dans la signature) orienté (les fils d'un nœud sont ordonnés de droite à gauche). Il y a de plus une contrainte, à savoir que le nombre de fils d'un nœud est donné par l'arité de l'étiquette du nœud. On parle de représentation arborescente d'un terme.

Un exemple

Considérons la signature

$\Sigma _{0}=X\cup \{0,1,2,...\}$ où $X=\{n,m,n',m'\}$
$\Sigma _{2}=\{+,*,/\}$
$\Sigma _{i}=\emptyset$ pour $0\neq i\neq 2$ .

Soit $t$ le terme tel que ${\mathit {Pos}}(t)=\{\varepsilon ,1,2,11,12,121,122\}$ et

$t(\varepsilon )=/$
$t(1)=*$
$t(2)=2$
$t(11)=n$
$t(12)=+$
$t(121)=n$
$t(122)=1$ .

Il s'agit du terme de gauche de la figure ci-dessus. Il s'écrit $/(*(n,+(n,1)),2)$ en notation récursive préfixée, $/*+n1n2$ en notation polonaise et $(n*(n+1))/2$ en notation infixe.

Quelques définitions liées aux termes

Le nombre d'éléments de ${\mathit {Pos}}(s)$ s'appelle la taille de $s$ . La position $\varepsilon$ (le mot vide de $(\mathbb {N} -\{0\})^{*}$ ) est la racine et $s(\varepsilon )$ est le symbole à la racine.

Un terme sans variable est dit clos ou fermé. Un terme qui n'est pas fermé est dit ouvert.

Le symbole à la position $p$ dans $t$ est le symbole de $\mathbf {\Sigma }$ associé à $p\in {\mathit {Pos}}(t)$ par la fonction $t:{\mathit {Pos}}(t)\rightarrow \mathbf {\Sigma }$ . Si $p\notin {\mathit {Pos}}(t)$ alors $t(p)$ , autrement dit le symbole à la position $p$ dans $t$ , n'est pas défini.

Si $p$ est une position de $t$ , le sous-terme de $t$ à la position $p$ s'écrit $t_{|p}$ et se définit comme suit. Les positions de $t_{|p}$ forment l'ensemble des suffixes de $p$ dans $Pos(t)$ , autrement dit:

Pos(t_{|p})=\{q\in (\mathbb {N} -\{0\})^{*}\mid pq\in Pos(t)\}

.

Enfin $t_{|p}(q)=t(pq)$ . La racine de $t_{|p}$ est le symbole à la position $p$ dans $t$ , autrement dit $t_{|p}(\varepsilon )=t(p)$ . Dans l'exemple ci-dessus, $t_{|p}$ est le terme $n+2$ .

Algèbre et algèbre des termes

L'enracinement est l'opération qui consiste à prendre un opérateur $f$ d'arité $n$ et $n$ termes $t_{1}$ , ..., $t_{n}$ et à créer un terme $f(t_{1},...,t_{n})$ . L'enracinement permet de munir l'ensemble des termes d'une structure d'algèbre universelle.

Il existe un morphisme naturel de l'algèbre des termes vers n'importe laquelle des algèbres de même signature. Ce morphisme fait de l'algèbre des termes sur une signature donnée $\mathbf {\Sigma }$ une algèbre initiale de la catégorie des algèbres de signature $\mathbf {\Sigma }$ .

Bibliographie

(en) Terese, Term Rewriting Systems, Cambridge Tracts in Theoretical Computer Science, 2003 (ISBN 0521391156)
(en) Franz Baader et Tobias Nipkow, Term Rewriting and All That, Cambridge (GB), Cambridge University Press, 1999 (1^re éd. 1998), 301 p. (ISBN 0-521-45520-0 et 0521779200, présentation en ligne)

Voir aussi

Notes & Références

↑ La tradition veut que la racine des arbres soit positionnée en haut!

[1] La tradition veut que la racine des arbres soit positionnée en haut!

[1]