Unification

En informatique et en logique, l'unification est un processus algorithmique qui, étant donnés deux termes, trouve une substitution qui appliquée aux deux termes les rend identiques^[1]. Par exemple, $x+3$ et $2+y$ peuvent être rendus identiques par la substitution $x:=2$ et $y:=3$ , qui donne quand on l'applique à chacun de ces termes le terme $2+3$ . Dit autrement, l'unification est la résolution d'une équation dans l'algèbre des termes (unification syntaxique) ou dans une algèbre quotient par un ensemble d'identités (unification modulo une théorie) ; la solution de l'équation est la substitution qui rend les deux termes identiques et que l'on appelle l'unificateur. L'unification a des applications en inférence de types, programmation logique, en démonstration automatique de théorèmes, en système de réécriture, en traitement du langage naturel^[1].

Unifier deux termes, c'est les rendre identiques en remplaçant les variables.

Souvent, on s'intéresse à l'unification syntaxique où il faut que les termes obtenus par application de l'unificateur soient syntaxiquement égaux, comme dans l'exemple ci-dessus. Par exemple, le problème d'unification syntaxique ayant pour données $x+3$ et $5$ n'a pas de solution^[2]. Le filtrage par motif (ou pattern matching) est une restriction de l'unification où l'unificateur n'est appliquée qu'à un seul des deux termes. Par exemple, $x+3$ et $2+3$ sont rendus égaux par la substitution $x:=2$ .

La fin de l'article présente aussi l'unification modulo une théorie, qui est le cas où on dispose de connaissances supplémentaires sur les fonctions (par exemple, $+$ est commutatif).

Histoire

John Alan Robinson, considéré comme le fondateur de l'unification.

Invention de la notion d'unification

Le premier chercheur à évoquer un algorithme d'unification est Jacques Herbrand dans sa thèse en 1930^[3]. Il s'agit d'un algorithme non-déterministe pour unifier deux termes. Herbrand était intéressé par la résolution d'équations. En 1960, Prawitz et Voghera^[4] ont généralisé le calcul propositionnel à des formules du premier ordre non instanciées, ou tout au moins en les instanciant a minima. L'unification a ensuite été redécouverte en 1963, mais l'article qui la décrit est publié seulement en 1965, par John Alan Robinson^[5]^,^[6] dans le cadre de sa méthode de résolution en démonstration automatique. Selon Baader et Snyder^[7], c'est Knuth et Bendix^[8]^,^[9], en 1970, qui ont introduit le concept de "substitution la plus générale" dans leur travail sur la confluence locale d'un système de réécriture. Un an avant la publication de l'article de Robinson, soit en 1964, Guard a indépendamment étudié le problème d'unification sous le nom de matching^[10].

Course vers l'efficacité

L'algorithme originel de Robinson est inefficace car il s'exécute en temps exponentiel et demande une quantité de mémoire exponentielle. Robinson écrit alors une note en 1971 où il exhibe une représentation des termes plus concise^[11]. L'algorithme utilise alors un espace mémoire polynomial. Boyer et Moore donnent aussi un algorithme qui utilise un espace mémoire polynomial en temps exponentiel dans le pire cas^[12]. Venturini-Zilli introduit un système de marquage pour que l'algorithme de Robinson s'exécute en temps quadratique, dans le pire cas, en la taille des termes^[13]. Huet travaille sur l'unification d'ordre supérieur et améliore le temps d'exécution de l'algorithme syntaxique du premier ordre : son algorithme est quasi linéaire^[14]. D'autres chercheurs ont exhibé des algorithmes quasi linéaires^[15]^,^[16]^,^[17].

Une étape importante est ensuite la découverte d'algorithmes linéaires en 1976 par Martelli et Montanari^[18], Paterson et Wegman^[19]^,^[20] et Huet^{[réf. nécessaire]}. Comme les articles de Paterson et Wegman sont courts, Dennis de Champeaux a réexpliqué l'idée de l'algorithme en 1986^[20].

En 1982, Martelli et Montanari présentent un algorithme presque-linéaire mais plus efficace en pratique^[21].

En 1984, Dwork et al. démontrent que l'unification est P-complet^[22], ce qui signifie qu'a priori l'unification est difficile à paralléliser. Par opposition, le problème de filtrage par motif (pattern matching) est dans NC^[22], c'est-à-dire facile à paralléliser.

Prolog a aussi beaucoup contribué à sa popularisation^[évasif]. Des algorithmes spécifiques pour les termes de certaines théories, appelés aussi unification équationnelle (en particulier associative et commutative par Stickel) ont été proposés (voir ci-dessus).

Description

Problèmes d'unification

Un problème d'unification peut être présenté comme la donnée de deux termes, ou alors comme une équation, ou alors comme un ensemble de termes à unifier, ou alors comme un ensemble de couples de termes, ou alors comme un ensemble d'équations. Le problème d'unification $f(x,y)=f(a,g(x))$ a une solution $x=a,y=g(a)$ car substituer (i.e. remplacer) le terme $a$ à la variable $x$ et le terme $g(a)$ à la variable $y$ , dans les deux termes $f(x,y)$ et $f(a,g(x))$ donne le même terme $f(a,g(a))$ . En revanche, le problème d'unification $f(x,y)=h(a,x)$ n'a pas de solution et le problème d'unification $x=g(x)$ non plus.

Solution principale

Un problème d'unification peut avoir une infinité de solutions. Par exemple, $f(a,x)=f(a,g(y))$ a une infinité de solutions : $x=g(f(a,a)),y=f(a,a)$ , $x=g(f(a,w)),y=f(a,w)$ , $x=g(z),y=z$ , etc. De toutes ces solutions, on exhibe des solutions dites principales car elles permettent de construire toutes les autres solutions : c'est le concept de solution principale, ou unificateur le plus général (most general unifier, mgu).

Tout d'abord, une solution $\sigma _{2}$ d'un problème d'unification est dite plus générale qu'une solution $\sigma _{1}$ , si $\sigma _{1}$ est obtenue en substituant des termes à des variables dans $\sigma _{2}$ . Par exemple, si on considère le problème d'unification $f(a,x)=f(a,g(y))$ , alors la solution $\sigma _{2}=(x=g(f(a,w)),y=f(a,w))$ est plus générale que la solution $\sigma _{1}=(x=g(f(a,a)),y=f(a,a))$ qui est obtenue en substituant le terme $a$ à la variable $w$ dans $\sigma _{2}$ . De même, la solution $\sigma _{3}=(x=g(z),y=z)$ est plus générale que la solution $\sigma _{2}$ , qui est obtenue en substituant le terme $f(a,w)$ à la variable $z$ dans la solution $\sigma _{3}$ .

Une solution $\sigma$ d'un problème d'unification est dite principale si elle est plus générale que toutes les solutions de ce problème, c'est-à-dire si toute solution est obtenue en substituant des termes à des variables dans $\sigma$ . Dans cet exemple, la solution $\sigma _{3}$ est une solution principale du problème $f(a,x)=f(a,g(y))$ .

Le théorème de la solution principale exprime que si un problème d'unification a une solution, alors il a une solution principale. Un algorithme d'unification calcule une solution principale ou échoue si les termes ne sont pas unifiables.

Exemples

La table suivante donne des exemples de problèmes d'unification. En plus, nous donnons aussi, dans la colonne de gauche, les exemples avec la syntaxe de Prolog : une variable commence par une majuscule, les constantes et symboles de fonction commencent par une minuscule. Pour les notations mathématiques, x,y,z sont des variables, , f,g sont des symboles de fonction et a,b sont des constantes.

Notation Prolog	Notation mathématique	Solution (principale)	Explication
`a = a`	{ a = a }	{}	L'unification réussit car nous avons le même symbole de constante a de part et d'autre de l'égalité.
`a = b`	{ a = b }	échoue	L'unification échoue. En effet, a et b sont des symboles de constantes différents Donc il est impossible de rendre les deux termes de part et d'autre de l'égalité syntaxiquement égaux.
`X = X`	{ x = x }	{}	L'unification réussit car nous avons la même variable de part et d'autre de l'égalité.
`a = X`	{ a = x }	{ x ↦ a }	La variable x est unifié avec la constante a.
`X = Y`	{ x = y }	{ x ↦ y }	La variable x est unifié avec y.
`f(a,X) = f(a,b)`	{ f(a,x) = f(a,b) }	{ x ↦ b }	Les symboles de fonction sont les mêmes. x est unifié avec la constante b
`f(a) = g(a)`	{ f(a) = g(a) }	échoue	f et g sont des symboles de fonction différents. On ne peut donc pas rendre les deux termes syntaxiquement égaux.
`f(X) = f(Y)`	{ f(x) = f(y) }	{ x ↦ y }	x est unifié avec y
`f(X) = g(Y)`	{ f(x) = g(y) }	échoue	f et g sont des symboles de fonction différents
`f(X) = f(Y,Z)`	{ f(x) = f(y,z) }	échoue	Le symbole de fonction f est d'arité 1 dans la partie gauche et d'arité 2 dans la partie droite.
`f(g(X)) = f(Y)`	{ f(g(x)) = f(y) }	{ y ↦ g(x) }	y est unifié avec g(x)
`f(g(X),X) = f(Y,a)`	{ f(g(x),x) = f(y,a) }	{ x ↦ a, y ↦ g(a) }	x est unifié avec la constante a, et y est unifié avec g(a)
`X = f(X)`	{ x = f(x) }	échoue	échoue car x apparaît dans f(x). Le test d'appartenance de x dans le terme droit f(x) s'appelle occur check. Il existe des implémentations de Prolog où il n'y a pas d'occur check. Pour ces dernières, on unifie x avec le terme infini `x=f(f(f(f(...))))`.
`X = Y, Y = a`	{ x = y, y = a }	{ x ↦ a, y ↦ a }	x et y sont unifiés avec la constante a
`a = Y, X = Y`	{ a = y, x = y }	{ x ↦ a, y ↦ a }	x et y sont unifiés avec la constante a
`X = a, b = X`	{ x = a, b = x }	échoue	a et b sont des symboles de constantes différents. x ne peut s'unifier avec les deux à la fois.

Applications

Filtrage par motif dans les langages de programmation

Article détaillé : Filtrage par motif.

Le filtrage par motif est la restriction de l'unification dans laquelle, dans chaque équation, les variables n'apparaissent que dans le terme de gauche. Par exemple, le problème $f(a,x)=f(a,g(b))$ est un problème de filtrage, car le terme $f(a,g(b))$ ne contient pas de variables. Le filtrage est utilisé dans les langages fonctionnels comme Haskell, Caml, LISP.

Dans le cas du filtrage, l'algorithme de Martelli et Montanari se simplifie.

On choisit une équation dans le système.

Si cette équation a la forme

f(t_{1},\ldots ,t_{n})=f(u_{1},\ldots ,u_{n})

on la remplace par les équations $t_{1}=u_{1}$ , ..., $t_{n}=u_{n}$ et on résout le système obtenu.

Si cette équation a la forme

f(t_{1},\ldots ,t_{n})=g(u_{1},\ldots ,u_{m})

où $f$ et $g$ sont des symboles différents, on échoue.

Si cette équation a la forme

x=t

on substitue le terme $t$ à la variable $x$ dans le reste du système, on résout le système obtenu, ce qui donne une solution $\sigma$ et on retourne la solution $\sigma ,x=t$ .

Programmation logique

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

L'unification est ce qui distingue le plus le langage de programmation Prolog des autres langages de programmation.

En Prolog, l’unification est associée au symbole « = » et ses règles sont les suivantes :

une variable X non-instanciée (c'est-à-dire ne possédant pas encore de valeur) peut être unifiée avec une autre variable (instanciée ou pas); les deux variables deviennent alors simplement des synonymes l'une de l'autre et représenteront dorénavant le même objet (ou la même structure) ;
une variable X non-instanciée peut être unifiée avec un terme ou un atome et représentera dorénavant ce terme ou atome ;
un atome peut être unifié seulement avec lui-même ;
un terme peut être unifié avec un autre terme : si leurs noms^[Quoi ?] sont identiques, si leur nombres d'arguments sont identiques et si chacun des arguments du premier terme est unifiable avec l'argument correspondant du second terme.

En raison de sa nature déclarative, l'ordre dans une suite d'unifications ne joue aucun rôle.

Algorithmes

Algorithme de Robinson

L'algorithme de Robinson de 1965 a été reformulé, par Corbin et Bidoit en 1983 ^[23], puis amélioré par Ruzicka et Prívara en 1989^[24], puis repris par Melvin Fitting en 1990 comme un algorithme non-déterministe^[25], présentation également reprise par Apt en 1996^[26]. Nous présentons cette version également. L'algorithme prend en entrée deux termes t1 et t2 à unifier, donnés sous la forme de deux arbres. Il repose sur la notion de disagreement pair qui est la donnée d'un sous-terme de t1 et d'un sous-terme de t2, dont les nœuds dans les arbres de t1 et t2 sont à la même position depuis les racines mais avec des étiquettes différentes. Une telle disagreement pair est simple si l'un des sous-termes est une variable qui n'apparaît pas dans l'autre sous-terme. L'algorithme calcule une substitution, initialement vide. L'algorithme continue tant que la substitution ne rend pas les deux termes égaux. Il choisit de façon non-déterministe un disagreement pair. S'il n'est pas simple, l'algorithme échoue. Sinon, il enrichit la substitution.

Pseudo-code de l'algorithme de Robinson

entrée : deux termes t1, t2
sortie : vrai si les termes sont unifiables, non sinon
fonction unifier(t1, t2)
      σ := id
      tant que  σ(t1) différent de σ(t2)
                 choisir une disagreement pair (w, u)
                 si (w, u) est simple
                           soit γ la substitution donnée par (w, u)
                           σ := σγ
                sinon
                        retourner faux;     
     retourner vrai

Algorithme de Martelli et Montanari

En 1982, Martelli et Montanari décrivent un algorithme sous la forme d'un ensemble de règles qui transforment un ensemble d'équations^[21]. L'algorithme est présenté dans des ouvrages pédagogiques^[27]^,^[28]^,^[29]. Il est similaire à l'algorithme proposé par Herbrand dans sa thèse^[30]. Selon Baader et Snyder^[31], un algorithme sous la forme d'un ensemble de règles dégage les concepts essentiels et permet de démontrer la correction de plusieurs algorithmes pratiques en même temps.

On se donne un ensemble fini d'équations G = { s₁ ≐ t₁, ..., s_n ≐ t_n } où les s_i et t_i sont des termes du premier ordre. L'objectif est de calculer une substitution la plus générale. On applique alors les règles suivantes à l'ensemble G jusqu'à épuisement :

G ∪ { t ≐ t }	⇒	G		supprimer
G ∪ { f(s₁,...,s_k) ≐ f(t₁,...,t_k) }	⇒	G ∪ { s₁ ≐ t₁, ..., s_k ≐ t_k }		décomposer
G ∪ { f(t⃗) ≐ x }	⇒	G ∪ { x ≐ f(t⃗) }		échanger
G ∪ { x ≐ t }	⇒	G{x↦t} ∪ { x ≐ t }	si x ∉ vars(t) et x ∈ vars(G)	éliminer

La règle supprimer supprime une équation t ≐ t, c'est-à-dire où les termes de la partie gauche et de la partie droite sont les mêmes. La règle décomposer supprime une équation de la forme f(s₁,...,s_k) ≐ f(t₁,...,t_k) et la remplace par les équations s₁ ≐ t₁, ..., s_k ≐ t_k. La règle échanger oriente les équations pour que la variable x soit en partie gauche. En présence d'une équation x ≐ t où la variable x n'apparaît pas dans le terme t, la règle éliminer remplace les occurrences de x par t dans les autres équations.

Les règles suivantes sont également ajoutées en guise d'optimisation^[29] :

G ∪ { f(s⃗) ≐ g(t⃗) }	⇒	⊥	si f ≠ g or k ≠ m	conflit
G ∪ { x ≐ f(s⃗) }	⇒	⊥	si x ∈ vars(f(s⃗))	vérifier (occurs-check)

Si l'ensemble contient une équation de la forme f(s⃗) ≐ g(t⃗) où f et g ne sont pas les mêmes symboles de fonctions ou alors si les nombres d'arguments ne sont pas les mêmes (k ≠ m) la règle conflit fait échouer le processus d'unification. La règle vérifier (occurs-check), quant à elle, fait échouer l'unification si l'ensemble contient une équation x ≐ f(s⃗) où x apparaît dans f(s⃗).

L'algorithme est en temps exponentiel et demande un espace mémoire au plus exponentiel si l'on représente les termes par leurs arbres syntaxiques. Néanmoins, on peut n'utiliser qu'un espace mémoire linéaire si on représente les termes par des graphes.

Améliorations de l'algorithme de Robinson

Implémentation avec des graphes

L'algorithme d'unification prend en entrée deux termes représentés par des graphes, ici f(x, g(x, x)) et f(h(y), g(z, h(1))). En sortie, une substitution la plus générale est représentée par des pointeurs (en bleu).

En implémentant l'algorithme avec des graphes, l'espace mémoire est linéaire en la taille de l'entrée même si le temps reste exponentiel dans le pire des cas. L'algorithme prend en entrée deux termes sous la forme de graphes, c'est-à-dire un graphe acyclique où les nœuds sont les sous-termes. En particulier, il y a un unique nœud par variables (cf. figure à droite). L'algorithme retourne en sortie une substitution la plus générale : elle est écrite en place dans le graphe représentant les termes à l'aide de pointeurs (en bleu dans la figure à droite). c'est-à-dire, en plus du graphe décrivant la structure des termes (qui sont des pointeurs aussi), nous avons des pointeurs particuliers pour représenter la substitution. Par exemple si x := h(1) est la substitution courante, x pointe vers le nœud correspondant au terme h(1).

Pseudo-code de l'implémentation avec des graphes

entrée : deux termes t1, t2
sortie : vrai si les termes sont unifiables, non sinon
fonction unifier(t1, t2)
      t1 = find(t1);
      t2 = find(t2);
      si t1 = t2
              retourner vrai;
      sinon etude de cas sur (t1, t2)
                (x, y):
                        faire pointer x vers y
                        retourner vrai;
                (x, t) ou (t, x):
                        si x apparaît dans t
                               retourner faux
                        sinon
                               faire pointer x vers t
                               retourner vrai;
               (f(L), g(M)):
                          si f = g
                                       retourner unifierlistes(L, M)
                          sinon
                                       retourner faux

où unifierListes unifient les termes de deux listes :

entrée : deux listes de termes L, M
sortie : vrai si les termes des listes sont deux à deux sont unifiables, non sinon
fonction unifierlistes(L, M)
            etude de cas sur (L, M)
                       ([], []): retourner vrai;
                       ([], t::t') ou (t::t', []): retourner faux;
                       (s::L', t::M'):
                                   si unifier(s, t)
                                             retourner unifierlistes(L', M')
                                   sinon
                                             retourner faux

où find trouve la fin d'une chaîne :

entrée : un terme t
sortie : le terme en bout de chaîne de t
fonction find(t)
         si t n'est pas une variable
                    retourner t
         sinon
                    si t est déjà assigné à un terme u
                           retourner find(u)
                    sinon
                           retourner t

et où une implémentation naïve de "x apparaît dans t" est donné par :

entrée : une variable x et un terme t
sortie : vrai si la variable x apparaît dans le terme t, non sinon
fonction apparaîtdans(x, t)
          etude de cas sur t
                    y: retourner x = y
                    f(L): retourner apparaîtdansliste(x, L)

entrée : une variable x et une liste de termes L
sortie : vrai si la variable x apparaît dans l'un des termes de L, non sinon
fonction apparaîtdansliste(x, L)
         etude de cas sur L
                   []: retourner faux
                   t::L':
                            si apparaîtdans(x, find(t))
                                         retourner vrai
                            sinon
                                         retourner apparaîtdansliste(x, L')

Algorithme quadratique

L'algorithme présenté dans cette sous-section est dû à Corbin et Bidoit (1983)^[32]. Pour avoir une complexité quadratique, il y a deux améliorations de l'algorithme précédent.

Tester qu'une variable apparaît dans un sous-terme

Le graphe des deux termes avec les pointeurs en bleu.

L'implémentation pour tester si une variable x apparaît dans un sous-terme t est a priori en temps exponentiel. L'idée est d'éviter de parcourir plusieurs fois les mêmes nœuds. On marque les nœuds visités comme dans un parcours en profondeur de graphe. Une fois un test d'appartenance effectué, il faut a priori démarquer les nœuds. Au lieu de cela, on les marque avec le "temps actuel". On ajoute alors un champ aux nœuds du graphe que l'on appelle poinçon qui contient le "temps actuel". Nous disposons d'une variable globale "temps actuel" qui est incrémenté à chaque test d'appartenance.

Pseudo-code de l'implémentation du test d'appartenance

entrée : une variable x et un terme t
sortie : vrai si la variable x apparaît dans le terme t, non sinon
fonction apparaîtdans(x, t)
               temps actuel := temps actuel + 1
               retourner apparaîtdans'(x, t)

entrée : une variable x et un terme t
sortie : vrai si la variable x apparaît dans le terme t, non sinon (ne change pas le temps)
fonction apparaîtdans'(x, t)
          etude de cas sur t
                    y: retourner x = y
                    f(s):
                                  si f(s) est poinçonné au temps actuel
                                              retourner faux
                                  sinon
                                              poinçonner f(s) au temps actuel
                                              retourner apparaîtdansliste(x, s)

entrée : une variable x et une liste de termes L
sortie : vrai si la variable x apparaît dans l'un des termes de t, non sinon
fonction apparaîtdansliste(x, L)
         etude de cas sur t
                   []: retourner faux
                   t::L':
                            si apparaîtdans'(x, find(t))
                                         retourner vrai
                            sinon
                                         retourner apparaîtdansliste(x, L')

Éviter des appels inutiles à unifier

Pour éviter des appels inutiles à la procédure qui cherche à unifier deux termes, on utilise des pointeurs pour tous les nœuds et pas seulement les variables. On peut montrer que le nombre d'appels à la procédure qui unifie est O(|A|) où |A| est le nombre d'arcs dans le graphe. Le traitement interne utilise un parcours de pointeurs "find" en O(|S|) où |S| est le nombre de sommets et un test d'appartenance d'une variable dans un terme qui est en O(|S|+|A|) = O(|A|) car le graphe est connexe. Donc l'algorithme est bien quadratique.

Pseudo-code de l'adaptation de la procédure d'unification

entrée : un terme t
sortie : le terme en bout de chaîne de t
fonction find(t)
            si t pointe vers un terme u
                   retourner find(u)
            sinon
                   retourner t

et

entrée : deux termes t1, t2
sortie : vrai si les termes sont unifiables, non sinon
fonction unifier(t1, t2)
      t1 = find(t1);
      t2 = find(t2);
      si t1 = t2
              retourner vrai;
      sinon etude de cas sur (t1, t2)
                (x, y):
                        faire pointer x vers y
                        retourner vrai;
                (x, t) ou (t, x):
                        si x apparaît dans t
                               retourner faux
                        sinon
                               faire pointer x vers t
                               retourner vrai;
               (f(L), g(M)):
                          si f = g
                                       faire pointer f(L) vers g(M)
                                       retourner unifierlistes(L, M)
                          sinon
                                       retourner faux

Algorithme quasi linéaire

L'algorithme^[29] est inspiré de l'algorithme quadratique de la section précédente. Le test de savoir si x apparaît dans t n'est plus effectué au cours de l'algorithme mais uniquement à la fin : à la fin, on vérifie que le graphe est acyclique. Enfin, les pointeurs de la substitution et "find" sont implémentés à l'aide d'une structure de données Union-find. Plus précisément, on conserve les pointeurs dans la structure mais on dispose en plus une structure annexe Union-find. Dans la structure de données Union-find, les classes d'équivalence ne contiennent soit que des variables soit que des termes complexes. Pour passer d'une variable à un terme complexe, on utilise les pointeurs éventuels qui sont dans le graphe.

Pseudo-code de la procédure d'unification qui utilise Union-find

entrée : deux termes t1, t2
sortie : vrai si les termes sont unifiables ou que le graphe final est acyclique, non sinon
fonction unifier(t1, t2)
      t1 = find(t1);
      t2 = find(t2);
      si t1 = t2
              retourner vrai;
      sinon etude de cas sur (t1, t2)
                (x, y):
                        Union(x, y)
                        retourner vrai;
                (x, t) ou (t, x):
                        si x apparaît dans t
                               retourner faux
                        sinon
                               faire pointer x vers t
                               retourner vrai;
               (f(L), g(M)):
                          si f = g
                                       Union(f(L), g(M))
                                       retourner unifierlistes(L, M)
                          sinon
                                       retourner faux

Construction de graphes à partir d'arbres

Pour construire un graphe à partir d'un arbre, on parcourt l'arbre et on utilise une table de symboles (implémenté avec une table de hachage ou un arbre binaire de recherche) pour les variables car il faut garantir l'unicité du nœud x pour une variable x.

Unification modulo une théorie

L'unification modulo une théorie, aussi appelée (unification équationnelle, E-unification, unification dans une théorie) est l'extension de l'unification syntaxique dans les cas où les opérateurs sont assujettis à des axiomes, formant une théorie E. Généralement cette théorie est décrite par un ensemble d'égalités universelles. Par exemple, une théorie E peut contenir l'identité $u*v=v*u$ où les variables $u$ et $v$ sont implicitement quantifiées universellement et qui dit que l'opérateur $*$ est commutatif. Dès lors, bien que les termes $x*a$ et $y*b$ ne soient pas syntaxiquement unifiables, ils sont E-unifiables :

	$x*a$	{x ↦ b, y ↦ a}
=	$b*a$		en appliquant la substitution
=	$a*b$		car $*$ est commutatif.
=	$y*b$	{x ↦ b, y ↦ a}	en appliquant la substitution

Exemple de théories E

Conventions de nommages des propriétés
∀ u,v,w	u(vw)	=	(uv)w	$A$	Associativité de *
∀ u,v	u*v	=	v*u	$C$	Commutativité de *
∀ u,v,w	u*(v+w)	=	uv+uw	$D l$	Distributivité gauche de * sur +
∀ u,v,w:	(v+w)*u	=	vu+wu	$D r$	Distributivité droite de * sur +
∀ u:	u*u	=	u	I	Idempotence de *
∀ u:	n*u	=	u	$N l$	n est élément neutre gauche de *
u:	u*n	=	u	$N r$	n est élément neutre droit de *

L'E-unification est décidable pour une théorie E s'il existe un algorithme pour cette théorie qui termine sur chaque entrée et résout le problème d'E-unification. Il est semi-décidable s'il existe un algorithme qui se termine pour les entrées qui ont une solution et qui peut boucler pour des équations sans solution.

L'E-unification est décidable pour les théories suivantes :

$A$ ^[33]
$A$ , $C$ ^[34]
$A$ , $C$ , $I$ ^[35]
$A$ , $C$ , $N l$ ^[36]^,^[35]
$A$ , $I$ ^[37]
$A$ , $N l$ $,$ $N r$ (monoïde)^[38]
$C$ ^[39]
Anneaux booléens^[40]^,^[41]
Groupes abéliens, avec des symboles supplémentaire (du moment qu'ils ne sont pas assujetti à des axiomes)^[42]
Algèbres modales K4^[43]

L'E-unification est semi-decidable pour les théories suivantes :

$A$ , $D l$ $,$ $D r$ ^[44]
$A$ , $C$ , $D l$ ^[36]^,^[45]
Anneaux commutatifs^[42]

Unification et logique d'ordre supérieur

Si on se place en logique d'ordre supérieur, c'est-à-dire si on s'autorise à utiliser des variables comme symboles de fonction ou comme prédicats, on perd la décidabilité et l'unicité de l'unificateur quand il existe. Au pire, deux termes peuvent même avoir une infinité d'unificateurs tous différents, dans le sens suivant: soit t et t´ deux termes qu'on veut unifier, il peut exister un ensemble infini U d'unificateurs de t et t´ tel que si σ et ρ sont dans U, alors σ n'est pas plus général que ρ et ρ n'est pas plus général que σ.

Liens externes

Outil interactif d'expérimentation de l'algorithme d'unification de Robinson.

Notes et références

↑ ^{a et b} Kevin Knight, « Unification: A Multidisciplinary Survey », ACM Comput. Surv., vol. 21, n^o 1,‎ 1^er mars 1989, p. 93–124 (ISSN 0360-0300, DOI 10.1145/62029.62030, lire en ligne, consulté le 13 mai 2017)
↑ Attention, $x:=2$ n'est pas une solution car les termes $2+3$ et $5$ sont syntaxiquement différents.
↑ Jacques Herbrand, « Recherches sur la théorie de la démonstration », Thèse,‎ 1930 (lire en ligne, consulté le 13 mai 2017)
↑ Dag Prawitz, Ha\a a kan Prawitz et Neri Voghera, « A Mechanical Proof Procedure and Its Realization in an Electronic Computer », J. ACM, vol. 7, n^o 2,‎ 1^er avril 1960, p. 102–128 (ISSN 0004-5411, DOI 10.1145/321021.321023, lire en ligne, consulté le 15 mai 2017)
↑ J. A. Robinson, « A Machine-Oriented Logic Based on the Resolution Principle », J. ACM, vol. 12, n^o 1,‎ 1^er janvier 1965, p. 23–41 (ISSN 0004-5411, DOI 10.1145/321250.321253, lire en ligne, consulté le 13 mai 2017)
↑ John Alan Robinson: Logic and Logic Programming. Commun. ACM 35(3): 40-65 (1992)
↑ Franz Baader et Wayne Snyder, Unification Theory, 1^er janvier 1999 (lire en ligne), p. 443
↑ DE Knuth et PB Bendix, Computational problems in abstract algebra, Pergamon Press, 1^er janvier 1970 (lire en ligne), p. 263–297
↑ Donald Knuth, All Questions Answered, 318. NOTICES OF THE AMS. VOLUME 49, NUMBER 3
↑ (en) James R. Guard, « AUTOMATED LOGIC FOR SEMI-AUTOMATED MATHEMATICS », Scientific report,‎ 30 mars 1964 (www.dtic.mil/dtic/tr/fulltext/u2/602710.pdf)
↑ « Computational logic: the unification computation | AITopics », sur aitopics.org (consulté le 13 mai 2017)
↑ « The sharing of structure in theorem-proving programs | AITopics », sur aitopics.org (consulté le 13 mai 2017)
↑ (en) M. Venturini Zilli, « Complexity of the unification algorithm for first-order expressions », CALCOLO, vol. 12, n^o 4,‎ 1^er décembre 1975, p. 361–371 (ISSN 0008-0624 et 1126-5434, DOI 10.1007/BF02575754, lire en ligne, consulté le 13 mai 2017)
↑ Gérard Huet, Résolution d’équations dans les langages d’ordre 1, 2 ..., Omega, Université Paris VII (lire en ligne)
↑ Jeffrey Scott Vitter et Roger A. Simons, « Parallel Algorithms for Unification and Other Complete Problems in P », Proceedings of the 1984 Annual Conference of the ACM on The Fifth Generation Challenge, ACM, aCM '84,‎ 1^er janvier 1984, p. 75–84 (ISBN 089791144X, DOI 10.1145/800171.809607, lire en ligne, consulté le 13 mai 2017)
↑ (en) « An algebraic semantics approach to the effective resolution of type equations - ScienceDirect », sur www.sciencedirect.com (consulté le 13 mai 2017)
↑ (en) Lewis Denver Baxter, An Efficient Unification Algorithm, Applied Analysis & Computer Science, 1973, 34 pages
↑ Martelli, Alberto et Montanari, Ugo, « Unification in linear time and space: a structured presentation », Internal note IEI-B76-16,‎ 1^er janvier 1976 (lire en ligne, consulté le 13 mai 2017)
↑ M. S. Paterson et M. N. Wegman, « Linear Unification », Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, ACM, sTOC '76,‎ 1^er janvier 1976, p. 181–186 (DOI 10.1145/800113.803646, lire en ligne, consulté le 13 mai 2017)
↑ ^{a et b} (en) « Linear unification - ScienceDirect », sur www.sciencedirect.com (consulté le 13 mai 2017)
↑ ^{a et b} Alberto Martelli et Ugo Montanari, « An Efficient Unification Algorithm », ACM Trans. Program. Lang. Syst., vol. 4, n^o 2,‎ 1^er avril 1982, p. 258–282 (ISSN 0164-0925, DOI 10.1145/357162.357169, lire en ligne, consulté le 13 mai 2017)
↑ ^{a et b} Cynthia Dwork, Paris Kanellakis et John C. Mitchell, « On the Sequential Nature of Unification », J. Log. Program., vol. 1, n^o 1,‎ 1^er septembre 1984, p. 35–50 (ISSN 0743-1066, DOI 10.1016/0743-1066(84)90022-0, lire en ligne, consulté le 13 mai 2017)
↑ Jacques Corbin, Michel Bidoit: A Rehabilitation of Robinson's Unification Algorithm. IFIP Congress 1983: 909-914
↑ Peter Ruzicka, Igor Prívara: An Almost Linear Robinson Unification Algorithm. Acta Inf. 27(1): 61-71 (1989)
↑ (en) Melvin Fitting, First-Order Logic and Automated Theorem Proving : Springer (DOI 10.1007/978-1-4612-2360-3, lire en ligne)
↑ (en) Krzysztof R. Apt, From Logic Programming to Prolog, Londres, Prentice-Hall, Inc., 1^er janvier 1996, 328 p. (ISBN 0-13-230368-X, lire en ligne)
↑ Alg.1, p.261. Leur règle (a) correspond à notre règle échanger, (b) à supprimer, (c) à décomposer et conflit, et (d) à éliminer et vérifier.
↑ René Lalement, Logique, réduction, résolution, Paris/Milan/Barcelone, Masson, 1990, 370 p. (ISBN 2-225-82104-6), p. 222
↑ ^{a b et c} Franz Baader et Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1^er janvier 1998, 301 p. (ISBN 0-521-45520-0, lire en ligne)
↑ (en) Krzysztof Apt, Principles of Constraint Programming, Cambridge, Cambridge University Press, 1^er janvier 2003, 407 p. (ISBN 0-521-82583-0, lire en ligne), p. 134 Bibliographic remarks
↑ Franz Baader et Wayne Snyder, Unification Theory, 1^er janvier 1999 (lire en ligne), p. 446
↑ Jacques Corbin et Michel Bidoit, « A Rehabilitation of Robinson's Unification Algorithm », IFIP congress,‎ 1^er janvier 1983, p. 909–914 (lire en ligne, consulté le 12 mai 2016)
↑ Gordon D. Plotkin, Lattice Theoretic Properties of Subsumption, Memorandum MIP-R-77, Univ. Edinburgh, Jun 1970
↑ Mark E. Stickel, A Unification Algorithm for Associative-Commutative Functions, J. Assoc. Comput. Mach., vol.28, no.3, pp. 423–434, 1981
↑ ^{a et b} F. Fages, Associative-Commutative Unification, J. Symbolic Comput., vol.3, no.3, pp. 257–275, 1987
↑ ^{a et b} En présence de $C$ , $N l$ et $N r$ sont equivalents, de même pour $D l$ et $D r$
↑ Franz Baader, Unification in Idempotent Semigroups is of Type Zero, J. Automat. Reasoning, vol.2, no.3, 1986
↑ J. Makanin, The Problem of Solvability of Equations in a Free Semi-Group, Akad. Nauk SSSR, vol.233, no.2, 1977
↑ (en) F. Fages, « Associative-Commutative Unification », J. Symbolic Comput., vol. 3, n^o 3,‎ 1987, p. 257–275 (DOI 10.1016/s0747-7171(87)80004-4)
↑ (en) Martin, U., Nipkow, T., Proc. 8th CADE, vol. 230, Jörg H. Siekmann, coll. « LNCS », 1986, 506–513 p., « Unification in Boolean Rings »
↑ (en) A. Boudet, J.P. Jouannaud et M. Schmidt-Schauß, « Unification of Boolean Rings and Abelian Groups », Journal of Symbolic Computation, vol. 8,‎ 1989, p. 449–477 (DOI 10.1016/s0747-7171(89)80054-9, lire en ligne)
↑ ^{a et b} Baader and Snyder (2001), p. 486.
↑ F. Baader and S. Ghilardi, Unification in modal and description logics, Logic Journal of the IGPL 19 (2011), no. 6, pp. 705–730.
↑ P. Szabo, Unifikationstheorie erster Ordnung (First Order Unification Theory), Thesis, Univ. Karlsruhe, West Germany, 1982
↑ Jörg H. Siekmann, Universal Unification, Proc. 7th Int. Conf. on Automated Deduction, Springer LNCS vol.170, pp. 1–42, 1984

Article lié

Anti-unification

Sur les autres projets Wikimedia :

unification, sur le Wiktionnaire

[:3-1] {a et b} Kevin Knight, « Unification: A Multidisciplinary Survey », ACM Comput. Surv., vol. 21, n^o 1,‎ 1^er mars 1989, p. 93–124 (ISSN 0360-0300, DOI 10.1145/62029.62030, lire en ligne, consulté le 13 mai 2017)

[2] Attention, $x:=2$ n'est pas une solution car les termes $2+3$ et $5$ sont syntaxiquement différents.

[3] Jacques Herbrand, « Recherches sur la théorie de la démonstration », Thèse,‎ 1930 (lire en ligne, consulté le 13 mai 2017)

[4] Dag Prawitz, Ha\a a kan Prawitz et Neri Voghera, « A Mechanical Proof Procedure and Its Realization in an Electronic Computer », J. ACM, vol. 7, n^o 2,‎ 1^er avril 1960, p. 102–128 (ISSN 0004-5411, DOI 10.1145/321021.321023, lire en ligne, consulté le 15 mai 2017)

[5] J. A. Robinson, « A Machine-Oriented Logic Based on the Resolution Principle », J. ACM, vol. 12, n^o 1,‎ 1^er janvier 1965, p. 23–41 (ISSN 0004-5411, DOI 10.1145/321250.321253, lire en ligne, consulté le 13 mai 2017)

[6] John Alan Robinson: Logic and Logic Programming. Commun. ACM 35(3): 40-65 (1992)

[:4-7] Franz Baader et Wayne Snyder, Unification Theory, 1^er janvier 1999 (lire en ligne), p. 443

[8] DE Knuth et PB Bendix, Computational problems in abstract algebra, Pergamon Press, 1^er janvier 1970 (lire en ligne), p. 263–297

[9] Donald Knuth, All Questions Answered, 318. NOTICES OF THE AMS. VOLUME 49, NUMBER 3

[10] (en) James R. Guard, « AUTOMATED LOGIC FOR SEMI-AUTOMATED MATHEMATICS », Scientific report,‎ 30 mars 1964 (www.dtic.mil/dtic/tr/fulltext/u2/602710.pdf)

[11] « Computational logic: the unification computation | AITopics », sur aitopics.org (consulté le 13 mai 2017)

[12] « The sharing of structure in theorem-proving programs | AITopics », sur aitopics.org (consulté le 13 mai 2017)

[13] (en) M. Venturini Zilli, « Complexity of the unification algorithm for first-order expressions », CALCOLO, vol. 12, n^o 4,‎ 1^er décembre 1975, p. 361–371 (ISSN 0008-0624 et 1126-5434, DOI 10.1007/BF02575754, lire en ligne, consulté le 13 mai 2017)

[14] Gérard Huet, Résolution d’équations dans les langages d’ordre 1, 2 ..., Omega, Université Paris VII (lire en ligne)

[15] Jeffrey Scott Vitter et Roger A. Simons, « Parallel Algorithms for Unification and Other Complete Problems in P », Proceedings of the 1984 Annual Conference of the ACM on The Fifth Generation Challenge, ACM, aCM '84,‎ 1^er janvier 1984, p. 75–84 (ISBN 089791144X, DOI 10.1145/800171.809607, lire en ligne, consulté le 13 mai 2017)

[16] (en) « An algebraic semantics approach to the effective resolution of type equations - ScienceDirect », sur www.sciencedirect.com (consulté le 13 mai 2017)

[17] (en) Lewis Denver Baxter, An Efficient Unification Algorithm, Applied Analysis & Computer Science, 1973, 34 pages

[18] Martelli, Alberto et Montanari, Ugo, « Unification in linear time and space: a structured presentation », Internal note IEI-B76-16,‎ 1^er janvier 1976 (lire en ligne, consulté le 13 mai 2017)

[19] M. S. Paterson et M. N. Wegman, « Linear Unification », Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, ACM, sTOC '76,‎ 1^er janvier 1976, p. 181–186 (DOI 10.1145/800113.803646, lire en ligne, consulté le 13 mai 2017)

[sciencedirect_0022000078900430-20] {a et b} (en) « Linear unification - ScienceDirect », sur www.sciencedirect.com (consulté le 13 mai 2017)

[:1-21] {a et b} Alberto Martelli et Ugo Montanari, « An Efficient Unification Algorithm », ACM Trans. Program. Lang. Syst., vol. 4, n^o 2,‎ 1^er avril 1982, p. 258–282 (ISSN 0164-0925, DOI 10.1145/357162.357169, lire en ligne, consulté le 13 mai 2017)

[:2-22] {a et b} Cynthia Dwork, Paris Kanellakis et John C. Mitchell, « On the Sequential Nature of Unification », J. Log. Program., vol. 1, n^o 1,‎ 1^er septembre 1984, p. 35–50 (ISSN 0743-1066, DOI 10.1016/0743-1066(84)90022-0, lire en ligne, consulté le 13 mai 2017)

[23] Jacques Corbin, Michel Bidoit: A Rehabilitation of Robinson's Unification Algorithm. IFIP Congress 1983: 909-914

[24] Peter Ruzicka, Igor Prívara: An Almost Linear Robinson Unification Algorithm. Acta Inf. 27(1): 61-71 (1989)

[25] (en) Melvin Fitting, First-Order Logic and Automated Theorem Proving : Springer (DOI 10.1007/978-1-4612-2360-3, lire en ligne)

[26] (en) Krzysztof R. Apt, From Logic Programming to Prolog, Londres, Prentice-Hall, Inc., 1^er janvier 1996, 328 p. (ISBN 0-13-230368-X, lire en ligne)

[27] Alg.1, p.261. Leur règle (a) correspond à notre règle échanger, (b) à supprimer, (c) à décomposer et conflit, et (d) à éliminer et vérifier.

[28] René Lalement, Logique, réduction, résolution, Paris/Milan/Barcelone, Masson, 1990, 370 p. (ISBN 2-225-82104-6), p. 222

[:0-29] {a b et c} Franz Baader et Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1^er janvier 1998, 301 p. (ISBN 0-521-45520-0, lire en ligne)

[30] (en) Krzysztof Apt, Principles of Constraint Programming, Cambridge, Cambridge University Press, 1^er janvier 2003, 407 p. (ISBN 0-521-82583-0, lire en ligne), p. 134 Bibliographic remarks

[31] Franz Baader et Wayne Snyder, Unification Theory, 1^er janvier 1999 (lire en ligne), p. 446

[32] Jacques Corbin et Michel Bidoit, « A Rehabilitation of Robinson's Unification Algorithm », IFIP congress,‎ 1^er janvier 1983, p. 909–914 (lire en ligne, consulté le 12 mai 2016)

[33] Gordon D. Plotkin, Lattice Theoretic Properties of Subsumption, Memorandum MIP-R-77, Univ. Edinburgh, Jun 1970

[34] Mark E. Stickel, A Unification Algorithm for Associative-Commutative Functions, J. Assoc. Comput. Mach., vol.28, no.3, pp. 423–434, 1981

[Fages.1987-35] {a et b} F. Fages, Associative-Commutative Unification, J. Symbolic Comput., vol.3, no.3, pp. 257–275, 1987

[LRequivC-36] {a et b} En présence de $C$ , $N l$ et $N r$ sont equivalents, de même pour $D l$ et $D r$

[37] Franz Baader, Unification in Idempotent Semigroups is of Type Zero, J. Automat. Reasoning, vol.2, no.3, 1986

[38] J. Makanin, The Problem of Solvability of Equations in a Free Semi-Group, Akad. Nauk SSSR, vol.233, no.2, 1977

[39] (en) F. Fages, « Associative-Commutative Unification », J. Symbolic Comput., vol. 3, n^o 3,‎ 1987, p. 257–275 (DOI 10.1016/s0747-7171(87)80004-4)

[40] (en) Martin, U., Nipkow, T., Proc. 8th CADE, vol. 230, Jörg H. Siekmann, coll. « LNCS », 1986, 506–513 p., « Unification in Boolean Rings »

[41] (en) A. Boudet, J.P. Jouannaud et M. Schmidt-Schauß, « Unification of Boolean Rings and Abelian Groups », Journal of Symbolic Computation, vol. 8,‎ 1989, p. 449–477 (DOI 10.1016/s0747-7171(89)80054-9, lire en ligne)

[Baader_and_Snyder_2001,_p._486-42] {a et b} Baader and Snyder (2001), p. 486.

[43] F. Baader and S. Ghilardi, Unification in modal and description logics, Logic Journal of the IGPL 19 (2011), no. 6, pp. 705–730.

[44] P. Szabo, Unifikationstheorie erster Ordnung (First Order Unification Theory), Thesis, Univ. Karlsruhe, West Germany, 1982

[45] Jörg H. Siekmann, Universal Unification, Proc. 7th Int. Conf. on Automated Deduction, Springer LNCS vol.170, pp. 1–42, 1984

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]