Unificación (informática)

Proceso algorítmico de resolución de ecuaciones.

En lógica e informática , la unificación es un proceso algorítmico de resolución de ecuaciones entre expresiones simbólicas , cada una de las cuales tiene la forma Lado izquierdo = Lado derecho .

Por ejemplo, usando x , y , z como variables, el conjunto de ecuaciones singleton { cons ( x , cons ( x , nil )) = cons (2, y )} es un problema sintáctico de unificación de primer orden que tiene la sustitución { x ↦ 2, y ↦ cons (2, nil ) } como única solución.

El razonamiento automatizado es el principal área de aplicación de la unificación. La unificación sintáctica de primer orden se utiliza en la programación lógica y la implementación de sistemas de tipos de lenguajes de programación , especialmente en algoritmos de inferencia de tipos basados ​​en Hindley-Milner . La unificación semántica se utiliza en solucionadores SMT , algoritmos de reescritura de términos y análisis de protocolos criptográficos . La unificación de orden superior (completa o restringida a la unificación de patrones de orden superior ) se utiliza en asistentes de prueba y programación lógica de orden superior, por ejemplo Isabelle , Twelf y lambdaProlog .

Definicion formal

Un problema de unificación es un conjunto finito E ={ l ₁ ≐ r ₁ , ..., l _n ≐ r _n } de ecuaciones a resolver, donde l _i , r _i están en el conjunto de términos o expresiones . Dependiendo de qué expresiones o términos se permiten que aparezcan en un conjunto de ecuaciones o un problema de unificación, y qué expresiones se consideran iguales, se distinguen varios marcos de unificación. Si en una expresión se permiten variables de orden superior, es decir, variables que representan funciones , el proceso se denomina unificación de orden superior ; de lo contrario, unificación de primer orden . Si se requiere una solución para hacer que ambos lados de cada ecuación sean literalmente iguales, el proceso se llama unificación sintáctica o libre ; de ​​lo contrario, unificación semántica o ecuacional , o unificación E , o teoría del módulo de unificación . ${\displaystyle T}$

Si el lado derecho de cada ecuación es cerrado (sin variables libres), el problema se llama coincidencia (de patrón) . El lado izquierdo (con variables) de cada ecuación se llama patrón . ^[1]

Requisitos previos

Formalmente, un enfoque de unificación presupone

• Un conjunto infinito de variables . Para la unificación de orden superior, es conveniente elegir variables disjuntas del conjunto de variables ligadas a términos lambda . ${\displaystyle V}$ ${\displaystyle V}$
• Un conjunto de términos tales que . Para la unificación de primer orden, suele ser el conjunto de términos de primer orden (términos construidos a partir de símbolos de variables y funciones). Porque la unificación de orden superior consta de términos de primer orden y términos lambda (términos que contienen algunas variables de orden superior). ${\displaystyle T}$ ${\displaystyle V\subseteq T}$ ${\displaystyle T}$ ${\displaystyle T}$
• Un mapeo vars : , asignando a cada término el conjunto de variables libres que ocurren en . ${\displaystyle T\rightarrow }$ ${\displaystyle \mathbb {P} }$ ${\displaystyle (V)}$ ${\displaystyle t}$ ${\displaystyle {\text{vars}}(t)\subsetneq V}$ ${\displaystyle t}$
• Una teoría o relación de equivalencia sobre , que indica qué términos se consideran iguales. Para la unificación E de primer orden, refleja el conocimiento previo sobre ciertos símbolos de función; por ejemplo, if se considera conmutativo, if resulta de intercambiar los argumentos de en algunas (posiblemente todas) ocurrencias. ^{[nota 1]} En el caso más típico en el que no existe ningún conocimiento previo, sólo literal o sintácticamente los términos idénticos se consideran iguales. En este caso, ≡ se llama teoría libre (porque es un objeto libre ), teoría vacía (porque el conjunto de oraciones ecuacionales , o el conocimiento previo, está vacío), teoría de funciones no interpretadas (porque la unificación se realiza en términos no interpretados ), o la teoría de los constructores (porque todos los símbolos de función simplemente construyen términos de datos, en lugar de operar sobre ellos). Para la unificación de orden superior, generalmente si y son equivalentes alfa . ${\displaystyle \equiv }$ ${\displaystyle T}$ ${\displaystyle \equiv }$ ${\displaystyle \oplus }$ ${\displaystyle t\equiv u}$ ${\displaystyle u}$ ${\displaystyle t}$ ${\displaystyle \oplus }$ ${\displaystyle t\equiv u}$ ${\displaystyle t}$ ${\displaystyle u}$

Como ejemplo de cómo el conjunto de términos y la teoría afecta el conjunto de soluciones, el problema de unificación sintáctica de primer orden { y = cons (2, y )} no tiene solución sobre el conjunto de términos finitos . Sin embargo, tiene una solución única { y ↦ cons (2, cons (2, cons (2,...))) } sobre el conjunto de términos de árbol infinitos . De manera similar, el problema de unificación semántica de primer orden { a ⋅ x = x ⋅ a } tiene cada sustitución de la forma { x ↦ a ⋅...⋅ a } como solución en un semigrupo , es decir, si (⋅) se considera asociativo . Pero el mismo problema, visto en un grupo abeliano , donde (⋅) se considera también conmutativo , tiene cualquier sustitución como solución.

Como ejemplo de unificación de orden superior, el conjunto singleton { a = y ( x ) } es un problema sintáctico de unificación de segundo orden, ya que y es una variable de función. Una solución es { x ↦ a , y ↦ ( función identidad ) }; otro es { y ↦ ( función constante que asigna cada valor a a ), x ↦ (cualquier valor) }.

Sustitución

Una sustitución es un mapeo de variables a términos; la notación se refiere a una sustitución que asigna cada variable al término , for y todas las demás variables a sí misma; deben ser distintos por pares. La aplicación de esa sustitución a un término se escribe en notación postfija como ; significa reemplazar (simultáneamente) cada aparición de cada variable en el término por . El resultado de aplicar una sustitución a un término se denomina instancia de ese término . Como ejemplo de primer orden, aplicando la sustitución { x ↦ h ( a , y ), z ↦ b } al término ${\displaystyle \sigma :V\rightarrow T}$ ${\displaystyle \{x_{1}\mapsto t_{1},...,x_{k}\mapsto t_{k}\}}$ ${\displaystyle x_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle i=1,...,k}$ ${\displaystyle x_{i}}$ ${\displaystyle t}$ ${\displaystyle t\{x_{1}\mapsto t_{1},...,x_{k}\mapsto t_{k}\}}$ ${\displaystyle x_{i}}$ ${\displaystyle t}$ ${\displaystyle t_{i}}$ ${\displaystyle t\tau }$ ${\displaystyle \tau }$ ${\displaystyle t}$ ${\displaystyle t}$

Generalización, especialización.

Si un término tiene una instancia equivalente a un término , es decir, si se trata de alguna sustitución , entonces se le llama más general que , y se le llama más especial que, o subsumido por ,. Por ejemplo, es más general que si ⊕ es conmutativo , desde entonces . ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle t\sigma \equiv u}$ ${\displaystyle \sigma }$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle t}$ ${\displaystyle x\oplus a}$ ${\displaystyle a\oplus b}$ ${\displaystyle (x\oplus a)\{x\mapsto b\}=b\oplus a\equiv a\oplus b}$

Si ≡ es identidad literal (sintáctica) de términos, un término puede ser más general y más especial que otro sólo si ambos términos difieren sólo en sus nombres de variables, no en su estructura sintáctica; dichos términos se denominan variantes o cambios de nombre entre sí. Por ejemplo, es una variante de , ya que ${\displaystyle f(x_{1},a,g(z_{1}),y_{1})}$ ${\displaystyle f(x_{2},a,g(z_{2}),y_{2})}$

$${\displaystyle f(x_{1},a,g(z_{1}),y_{1})\{x_{1}\mapsto x_{2},y_{1}\mapsto y_{2},z_{1}\mapsto z_{2}\}=f(x_{2},a,g(z_{2}),y_{2})}$$

$${\displaystyle f(x_{2},a,g(z_{2}),y_{2})\{x_{2}\mapsto x_{1},y_{2}\mapsto y_{1},z_{2}\mapsto z_{1}\}=f(x_{1},a,g(z_{1}),y_{1}).}$$

no ${\displaystyle f(x_{1},a,g(z_{1}),y_{1})}$ ${\displaystyle f(x_{2},a,g(x_{2}),x_{2})}$

Para arbitrario , un término puede ser a la vez más general y más especial que un término estructuralmente diferente. Por ejemplo, si ⊕ es idempotente , es decir, si siempre , entonces el término es más general que , ^{[nota 2]} y viceversa, ^{[nota 3]} aunque y sean de diferente estructura. ${\displaystyle \equiv }$ ${\displaystyle x\oplus x\equiv x}$ ${\displaystyle x\oplus y}$ ${\displaystyle z}$ ${\displaystyle x\oplus y}$ ${\displaystyle z}$

Una sustitución es más especial o está subsumida por una sustitución si está subsumida por para cada término . También decimos que es más general que . Más formalmente, tome un conjunto infinito no vacío de variables auxiliares tal que ninguna ecuación en el problema de unificación contenga variables de . Entonces una sustitución es subsumida por otra sustitución si hay una sustitución tal que para todos los términos , . ^[2] Por ejemplo , está subsumido por , usando , pero no está subsumido por , ya que no es una instancia de . ^[3] ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle t\sigma }$ ${\displaystyle t\tau }$ ${\displaystyle t}$ ${\displaystyle \tau }$ ${\displaystyle \sigma }$ ${\displaystyle V}$ ${\displaystyle l_{i}\doteq r_{i}}$ ${\displaystyle V}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \theta }$ ${\displaystyle X\notin V}$ ${\displaystyle X\sigma \equiv X\tau \theta }$ ${\displaystyle \{x\mapsto a,y\mapsto a\}}$ ${\displaystyle \tau =\{x\mapsto y\}}$ ${\displaystyle \theta =\{y\mapsto a\}}$ ${\displaystyle \sigma =\{x\mapsto a\}}$ ${\displaystyle \tau =\{x\mapsto y\}}$ ${\displaystyle f(x,y)\sigma =f(a,y)}$ ${\displaystyle f(x,y)\tau =f(y,y)}$

Conjunto de soluciones

Una sustitución σ es una solución del problema de unificación E si l _i σ ≡ r _i σ para . Esta sustitución también se denomina unificador de E. Por ejemplo, si ⊕ es asociativo , el problema de unificación { x ⊕ a ≐ a ⊕ x } tiene las soluciones { x ↦ a }, { x ↦ a ⊕ a }, { x ↦ a ⊕ a ⊕ a }, etc. mientras que el problema { x ⊕ a ≐ a } no tiene solución. ${\displaystyle i=1,...,n}$

Para un problema de unificación dado E , un conjunto S de unificadores se llama completo si cada sustitución de solución está subsumida por alguna sustitución en S. Siempre existe un conjunto de sustitución completo (por ejemplo, el conjunto de todas las soluciones), pero en algunos marcos (como la unificación ilimitada de orden superior) el problema de determinar si existe alguna solución (es decir, si el conjunto de sustitución completo no está vacío) es indecidible.

El conjunto S se llama mínimo si ninguno de sus miembros subsume a otro. Dependiendo del marco, un conjunto de sustitución completo y mínimo puede tener cero, uno, un número finito o un número infinito de miembros, o puede no existir en absoluto debido a una cadena infinita de miembros redundantes. ^[4] Así, en general, los algoritmos de unificación calculan una aproximación finita del conjunto completo, que puede ser mínima o no, aunque la mayoría de los algoritmos evitan unificadores redundantes cuando es posible. ^[2] Para la unificación sintáctica de primer orden, Martelli y Montanari ^[5] dieron un algoritmo que informa la insolubilidad o calcula un unificador único que por sí solo forma un conjunto de sustitución mínimo y completo, llamado el unificador más general .

Unificación sintáctica de términos de primer orden.

Diagrama triangular esquemático de los términos que unifican sintácticamente t ₁ y t ₂ mediante una sustitución σ

La unificación sintáctica de términos de primer orden es el marco de unificación más utilizado. Se basa en que T es el conjunto de términos de primer orden (sobre un conjunto dado V de variables, C de constantes y F _n de símbolos de funciones n -arias) y en que ≡ es la igualdad sintáctica . En este marco, cada problema de unificación resoluble { l ₁ ≐ r ₁ , ..., l _n ≐ r _n } tiene un conjunto de soluciones singleton completo, y obviamente mínimo, { σ } . Su miembro σ se denomina unificador más general ( mgu ) del problema. Los términos en el lado izquierdo y derecho de cada ecuación potencial se vuelven sintácticamente iguales cuando se aplica mgu, es decir, l ₁ σ = r ₁ σ ∧ ... ∧ l _n σ = r _n σ . Cualquier unificador del problema está subsumido ^{[nota 4]} por el mgu σ . El mgu es único salvo variantes: si S ₁ y S ₂ son conjuntos de solución completos y mínimos del mismo problema de unificación sintáctica, entonces S ₁ = { σ ₁ } y S ₂ = { σ ₂ } para algunas sustituciones σ ₁ y σ ₂ , y xσ ₁ es una variante de xσ ₂ para cada variable x que ocurre en el problema.

Por ejemplo, el problema de unificación { x ≐ z , y ≐ f ( x ) } tiene un unificador { x ↦ z , y ↦ f ( z ) }, porque

Este es también el unificador más general. Otros unificadores para el mismo problema son, por ejemplo, { x ↦ f ( x ₁ ), y ↦ f ( f ( x ₁ ) ), z ↦ f ( x ₁ ) }, { x ↦ f ( f ( x ₁ ) ), y ↦ f ( f ( f ( x ₁ )) ), z ↦ f ( f ( x ₁ )) }, y así sucesivamente; hay infinitos unificadores similares.

Como otro ejemplo, el problema g ( x , x ) ≐ f ( y ) no tiene solución con respecto a que ≡ sea identidad literal, ya que cualquier sustitución aplicada al lado izquierdo y derecho mantendrá los g y f más externos , respectivamente, y Los términos con diferentes símbolos de función más externos son sintácticamente diferentes.

Algoritmos de unificación

Algoritmo de unificación de Robinson de 1965

Los símbolos están ordenados de manera que las variables preceden a los símbolos de función. Los términos se ordenan aumentando la extensión escrita; Los términos igualmente largos se ordenan lexicográficamente . ^[6] Para un conjunto T de términos, su camino de desacuerdo p es el camino lexicográficamente mínimo donde dos términos miembros de T difieren. Su conjunto de desacuerdo es el conjunto de subtérminos que comienzan en p , formalmente: { t | _pag  : ${\displaystyle t\in T}$ }. ^[7]

Algoritmo: ^[8]
Given a set T of terms to be unified
Let ${\displaystyle \sigma }$ initially be the identity substitution
do forever
    if ${\displaystyle T\sigma }$ is a singleton set then
        return ${\displaystyle \sigma }$
    fi
    let D be the disagreement set of ${\displaystyle T\sigma }$
    let s, t be the two lexicographically least terms in D
    if s is not a variable or s occurs in t then
        return "NONUNIFIABLE"
    fi
    ${\displaystyle \sigma :=\sigma \{s\mapsto t\}}$
done

Jacques Herbrand discutió los conceptos básicos de unificación y esbozó un algoritmo en 1930. ^{[9] [10] [11]} Pero la mayoría de los autores atribuyen el primer algoritmo de unificación a John Alan Robinson (ver recuadro). ^{[12] [13] [nota 5]} El algoritmo de Robinson tuvo el peor comportamiento exponencial tanto en el tiempo como en el espacio. ^{[11] [15]} Numerosos autores han propuesto algoritmos de unificación más eficientes. ^[16] Martelli y Montanari (1976) y Paterson y Wegman (1976) descubrieron de forma independiente algoritmos con el peor comportamiento en tiempo lineal. ^{[nota 6]} Baader y Snyder (2001) utilizan una técnica similar a la de Paterson-Wegman, por lo que es lineal, pero como la mayoría de los algoritmos de unificación de tiempo lineal es más lento que la versión de Robinson en entradas de tamaño pequeño. ^[17] de Champeaux (2022) tiene una complejidad lineal en el tamaño de entrada, pero también es competitivo con el algoritmo de Robinson en entradas de tamaño pequeño. Champeaux atribuye la aceleración al uso de técnicas de programación orientada a objetos para evitar el preprocesamiento y la construcción de un DAG . ^[15]

El siguiente algoritmo se presenta comúnmente y se origina en Martelli y Montanari (1982). ^{[nota 7]} Dado un conjunto finito de ecuaciones potenciales, el algoritmo aplica reglas para transformarlo en un conjunto equivalente de ecuaciones de la forma { x ₁ ≐ u ₁ , ..., x _m ≐ u _m } donde x ₁ , . .., x _m son variables distintas y u ₁ , ..., u _m son términos que no contienen ninguno de los x _i . Un conjunto de esta forma puede leerse como una sustitución. Si no hay solución el algoritmo termina con ⊥; otros autores utilizan "Ω", o " fallar " en ese caso. La operación de sustituir todas las apariciones de la variable x en el problema G con el término t se denota G { x ↦ t }. Por simplicidad, los símbolos constantes se consideran símbolos de función que tienen cero argumentos. ${\displaystyle G=\{s_{1}\doteq t_{1},...,s_{n}\doteq t_{n}\}}$

ocurre cheque

Un intento de unificar una variable x con un término que contenga a x como un subtérmino estricto x ≐ f (..., x , ...) conduciría a un término infinito como solución para x , ya que x ocurriría como un subtérmino de sí mismo . En el conjunto de términos (finitos) de primer orden definidos anteriormente, la ecuación x ≐ f (..., x , ...) no tiene solución; por lo tanto, la regla de eliminación sólo puede aplicarse si x ∉ vars ( t ). Dado que esa verificación adicional, llamada verificación de ocurrencia , ralentiza el algoritmo, se omite, por ejemplo, en la mayoría de los sistemas Prolog. Desde un punto de vista teórico, omitir la verificación equivale a resolver ecuaciones sobre árboles infinitos, consulte #Unificación de términos infinitos a continuación.

Prueba de rescisión

Para la prueba de terminación del algoritmo, considere un triple donde n _var es el número de variables que ocurren más de una vez en el conjunto de ecuaciones, n _lhs es el número de símbolos de función y constantes en el lado izquierdo de las ecuaciones potenciales, y n _eqn es el número de ecuaciones. Cuando se aplica la regla de eliminación , n _var disminuye, ya que x se elimina de G y se mantiene solo en { x ≐ t }. La aplicación de cualquier otra regla nunca podrá volver a aumentar n _var . Cuando se aplica la regla de descomposición , conflicto o intercambio , n _lhs disminuye, ya que al menos la f más externa del lado izquierdo desaparece. La aplicación de cualquiera de las reglas restantes, eliminar o verificar, no puede aumentar n _lhs , pero disminuye n _eqn . De ahí que cualquier aplicación de regla disminuya el triple respecto del orden lexicográfico , lo cual es posible sólo un número finito de veces. ${\displaystyle \langle n_{var},n_{lhs},n_{eqn}\rangle }$ ${\displaystyle \langle n_{var},n_{lhs},n_{eqn}\rangle }$

Conor McBride observa ^[18] que "al expresar la estructura que explota la unificación" en un lenguaje de tipo dependiente como Epigram , el algoritmo de unificación de Robinson puede hacerse recursivo en el número de variables , en cuyo caso una prueba de terminación separada se vuelve innecesaria.

Ejemplos de unificación sintáctica de términos de primer orden.

En la convención sintáctica de Prolog, un símbolo que comienza con una letra mayúscula es un nombre de variable; un símbolo que comienza con una letra minúscula es un símbolo de función; la coma se utiliza como operador lógico y . Para la notación matemática, x,y,z se utilizan como variables, f,g como símbolos de función y a,b como constantes.

Dos términos con un árbol exponencialmente más grande como su instancia menos común. Su representación dag (parte naranja más a la derecha) todavía tiene un tamaño lineal.

El unificador más general de un problema de unificación sintáctica de primer orden de tamaño n puede tener un tamaño de 2 ⁿ . Por ejemplo, el problema tiene el unificador más general , cf. imagen. Para evitar la complejidad temporal exponencial causada por tal explosión, los algoritmos de unificación avanzados funcionan en gráficos acíclicos dirigidos (dags) en lugar de árboles. ^[19] ${\displaystyle (((a*z)*y)*x)*w\doteq w*(x*(y*(z*a)))}$ ${\displaystyle \{z\mapsto a,y\mapsto a*a,x\mapsto (a*a)*(a*a),w\mapsto ((a*a)*(a*a))*((a*a)*(a*a))\}}$

Aplicación: unificación en programación lógica.

El concepto de unificación es una de las ideas principales detrás de la programación lógica . Específicamente, la unificación es un componente básico de la resolución , una regla de inferencia para determinar la satisfacibilidad de la fórmula. En Prolog , el símbolo de igualdad =implica una unificación sintáctica de primer orden. Representa el mecanismo de vinculación del contenido de las variables y puede verse como una especie de asignación única.

En prólogo:

1. Una variable se puede unificar con una constante, un término u otra variable, convirtiéndose así efectivamente en su alias. En muchos dialectos Prolog modernos y en la lógica de primer orden , una variable no se puede unificar con un término que la contiene; Esta es la llamada verificación de ocurrencia .
2. Dos constantes sólo pueden unificarse si son idénticas.
3. De manera similar, un término se puede unificar con otro término si los símbolos de función superior y las aridades de los términos son idénticos y si los parámetros se pueden unificar simultáneamente. Tenga en cuenta que este es un comportamiento recursivo.
4. La mayoría de las operaciones, incluidas +, -, *, /, no son evaluadas por =. Entonces, por ejemplo, 1+2 = 3no es satisfactorio porque son sintácticamente diferentes. El uso de restricciones aritméticas de números enteros #=introduce una forma de unificación E para la cual estas operaciones se interpretan y evalúan. ^[20]

Aplicación: inferencia de tipos

Los algoritmos de inferencia de tipos generalmente se basan en la unificación, particularmente la inferencia de tipos Hindley-Milner que utilizan los lenguajes funcionales Haskell y ML . Por ejemplo, al intentar inferir el tipo de expresión de Haskell True : ['x'], el compilador utilizará el tipo a -> [a] -> [a]de función de construcción de lista (:), el tipo Booldel primer argumento Truey el tipo [Char]del segundo argumento ['x']. La variable de tipo polimórfico ase unificará con Booly el segundo argumento [a]se unificará con [Char]. ano puede ser ambas cosas Boolal Charmismo tiempo, por lo tanto, esta expresión no está escrita correctamente.

Al igual que Prolog, se puede proporcionar un algoritmo para la inferencia de tipos:

1. Cualquier variable de tipo se unifica con cualquier expresión de tipo y se crea una instancia de esa expresión. Una teoría específica podría restringir esta regla con una verificación de ocurrencia.
2. Dos constantes de tipo se unifican sólo si son del mismo tipo.
3. Dos construcciones de tipos se unifican sólo si son aplicaciones del mismo tipo constructor y todos sus tipos de componentes se unifican de forma recursiva.

Aplicación: Unificación de estructura de características

La unificación se ha utilizado en diferentes áreas de investigación de la lingüística computacional. ^{[21] [22]}

Unificación ordenada por orden

La lógica de ordenación permite asignar una clasificación , o tipo , a cada término y declarar una clasificación s ₁ como una subclasificación de otra clasificación s ₂ , comúnmente escrita como s ₁ ⊆ s ₂ . Por ejemplo, cuando se razona sobre criaturas biológicas, es útil declarar que un perro tipo es un subtipo de un animal tipo . Siempre que se requieraun término de algún tipo s , se puede suministrar en su lugar un término de cualquier subtipo de s . Por ejemplo, asumiendo una declaración de función madre : animal → animal , y una declaración constante lassie : perro , el término madre ( lassie ) es perfectamente válido y tiene el tipo animal . Para proporcionar la información de que la madre de un perro es a su vez un perro,se podrá emitir otra declaración madre : perro → perro ; esto se llama sobrecarga de funciones , similar a la sobrecarga en los lenguajes de programación .

Walther dio un algoritmo de unificación para términos en lógica ordenada, requiriendo que para dos tipos declarados s ₁ , s ₂ también se declarara su intersección s ₁ ∩ s _{2 : si} x ₁ y x ₂ es una variable de tipo s ₁ y s ₂ , respectivamente, la ecuación x ₁ ≐ x ₂ tiene la solución { x ₁ = x , x ₂ = x }, donde x : s ₁ ∩ s ₂ .^[23] Después de incorporar este algoritmo en un demostrador de teoremas automatizado basado en cláusulas, pudo resolver un problema de referencia traduciéndolo a lógica ordenada por orden, reduciéndolo así a un orden de magnitud, ya que muchos predicados unarios se convirtieron en géneros.

Smolka generalizó la lógica ordenada para permitir el polimorfismo paramétrico .^[24] En su marco, las declaraciones de subclasificación se propagan a expresiones de tipo complejo. Como ejemplo de programación, se puede declarar una lista de clasificación paramétrica ( X ) (siendo X un parámetro de tipo como en una plantilla de C++ ), y a partir de una declaración de subclasificación int ⊆ float la relación lista ( int ) ⊆ lista ( float ) se obtiene automáticamente. inferido, lo que significa que cada lista de números enteros es también una lista de flotantes.

Schmidt-Schauß generalizó la lógica ordenada para permitir declaraciones de términos.^[25] Como ejemplo, suponiendo declaraciones de subclasificación par ⊆ int e impar ⊆ int , una declaración de término como ∀ i  : int . ( i + i ): incluso permite declarar una propiedad de suma de enteros que no podría expresarse mediante sobrecarga ordinaria.

Unificación de términos infinitos

Antecedentes sobre árboles infinitos:

• B. Courcelle (1983). "Propiedades fundamentales de los árboles infinitos". Teoría. Computadora. Ciencia . 25 (2): 95-169. doi : 10.1016/0304-3975(83)90059-2 .
• Michael J. Maher (julio de 1988). "Axiomatizaciones completas de las álgebras de árboles finitos, racionales e infinitos". Proc. IEEE 3er Simposio Anual. sobre Lógica en Informática, Edimburgo . págs. 348–357.
• Joxan Jaffar; Peter J. Stuckey (1986). "Semántica de la programación lógica de árbol infinito". Informática Teórica . 46 : 141-158. doi : 10.1016/0304-3975(86)90027-7 .

Algoritmo de unificación, Prolog II:

• A. Colmerauer (1982). KL Clark; S.-A. Tarnlund (eds.). Prólogo y Árboles Infinitos . Prensa académica.
• Alain Colmerauer (1984). "Ecuaciones e inecuaciones sobre árboles finitos e infinitos". En ICOT (ed.). Proc. En t. Conf. sobre Sistemas Informáticos de Quinta Generación . págs. 85–99.

Aplicaciones:

• Francisco Giannesini; Jacques Cohen (1984). "Generación de analizadores y manipulación de gramática utilizando árboles infinitos de Prolog". Revista de programación lógica . 1 (3): 253–265. doi : 10.1016/0743-1066(84)90013-X .

Unificación electrónica

La e-unificación es el problema de encontrar soluciones a un conjunto dado de ecuaciones , teniendo en cuenta algunos conocimientos previos sobre ecuaciones E. Este último se da como un conjunto de igualdades universales . Para algunos conjuntos particulares E , se han ideado algoritmos de resolución de ecuaciones (también conocidos como algoritmos de unificación E ); para otros, se ha demostrado que tales algoritmos no pueden existir.

Por ejemplo, si a y b son constantes distintas, la ecuación no tiene solución con respecto a la unificación puramente sintáctica , donde no se sabe nada sobre el operador . Sin embargo, si se sabe que es conmutativo , entonces la sustitución { x ↦ b , y ↦ a } resuelve la ecuación anterior, ya que ${\displaystyle x*a\doteq y*b}$ ${\displaystyle *}$ ${\displaystyle *}$

El conocimiento previo E podría establecer la conmutatividad de por la igualdad universal " para todo u , v ". ${\displaystyle *}$ ${\displaystyle u*v=v*u}$

Conjuntos particulares de conocimientos previos E

Se dice que la unificación es decidible para una teoría, si se ha ideado un algoritmo de unificación que termine para cualquier problema de entrada. Se dice que la unificación es semidecidible para una teoría, si se ha ideado un algoritmo de unificación que termine para cualquier problema de entrada con solución , pero que pueda seguir buscando para siempre soluciones de un problema de entrada sin solución.

La unificación es decidible para las siguientes teorías:

• Un ^[26]
• A , C ^[27]
• A , C , I ^[28]
• A , C , N _l ^{[nota 9] [28]}
• A , yo ^[29]
• A , N _l , N _r (monoide) ^[30]
• C ^[31]
• Anillos booleanos ^{[32] [33]}
• Grupos abelianos , incluso si la firma se expande mediante símbolos adicionales arbitrarios (pero no axiomas) ^[34]
• Álgebras modales K4 ^[35]

La unificación es semidecidible para las siguientes teorías:

• A , D _l , Dr ^[36 _]
• A , C , D _l ^{[nota 9] [37]}
• Anillos conmutativos ^[34]

Paramodulación unilateral

Si hay un sistema de reescritura de términos convergente R disponible para E , el algoritmo de paramodulación unilateral ^[38] se puede utilizar para enumerar todas las soluciones de ecuaciones dadas.

Comenzando con G como el problema de unificación a resolver y S como la sustitución de identidad, las reglas se aplican de manera no determinista hasta que el conjunto vacío aparece como el G real , en cuyo caso el S real es una sustitución unificadora. Dependiendo del orden en que se aplican las reglas de paramodulación, de la elección de la ecuación real de G y de la elección de las reglas de R en mutación , son posibles diferentes caminos de cálculo. Sólo algunos conducen a una solución, mientras que otros terminan en G ≠ {} donde no se aplica ninguna otra regla (por ejemplo, G = { f (...) ≐ g (...) }).

Por ejemplo, se utiliza un término sistema de reescritura R para definir el operador de adición de listas creadas a partir de cons y nil ; donde cons ( x , y ) se escribe en notación infija como x . y por brevedad; por ejemplo , aplicación ( a.b.nil , c.d.nil ) → a .​​​​​ aplicación ( b . nil , c . d . nil ) → a . b . aplicación ( nil , c.d.nil ) → a .​​​ b . C . d . nil demuestra la concatenación de las listas a . b . nulo y c . d . nulo , empleando la regla de reescritura 2,2 y 1. La teoría ecuacional E correspondiente a R es el cierre de congruencia de R , ambos vistos como relaciones binarias en términos. Por ejemplo, aplicación ( a . b . nil , c . d . nil ) ≡ a . b . C . d . nil ≡ aplicación ( a . b . c . d . nil , nil ). El algoritmo de paramodulación enumera soluciones a ecuaciones con respecto a E cuando se alimenta con el ejemplo R.

Un ejemplo exitoso de ruta de cálculo para el problema de unificación { app ( x , app ( y , x )) ≐ a . a . nil } se muestra a continuación. Para evitar conflictos de nombres de variables, las reglas de reescritura se renombran constantemente cada vez antes de su uso mediante rule mutate ; v ₂ , v ₃ , ... son nombres de variables generados por computadora para este propósito. En cada línea, la ecuación elegida de G está resaltada en rojo. Cada vez que se aplica la regla de mutación , la regla de reescritura elegida ( 1 o 2 ) se indica entre paréntesis. Desde la última línea, la sustitución unificadora S = { y ↦ nil , x ↦ a . nil } se puede obtener. De hecho, app ( x , app ( y , x )) { y ↦ nil , x ↦ a . nil } = aplicación ( a . nil , aplicación ( nil , a . nil )) ≡ aplicación ( a . nil , a . nil ) ≡ a . aplicación ( nil , a.nil ) ≡ a .​ a . nil resuelve el problema dado. Una segunda ruta de cálculo exitosa, que se puede obtener eligiendo "mutar(1), mutar(2), mutar(2), mutar(1)" conduce a la sustitución S = { y ↦ a . a . nulo , x ↦ nulo }; no se muestra aquí. Ningún otro camino conduce al éxito.

Estrechamiento

Diagrama triangular del paso de estrechamiento s ↝ t en la posición p en el término s , con sustitución unificadora σ (fila inferior), usando una regla de reescritura l → r (fila superior)

Si R es un sistema de reescritura de términos convergente para E , un enfoque alternativo a la sección anterior consiste en la aplicación sucesiva de " pasos de estrechamiento "; esto eventualmente enumerará todas las soluciones de una ecuación dada. Un paso de estrechamiento (ver imagen) consiste en

• elegir un subtérmino no variable del término actual,
• unificándolo sintácticamente con el lado izquierdo de una regla de R , y
• reemplazando el lado derecho de la regla instanciada en el término instanciado.

Formalmente, si l → r es una copia renombrada de una regla de reescritura de R , que no tiene variables en común con un término s , y el subtérmino s | _p no es una variable y es unificable con l a través de mgu σ , entonces s puede reducirse al término t = sσ [ rσ ] _p , es decir, al término sσ , con el subtérmino en p reemplazado por rσ . La situación en la que s puede reducirse a t se denota comúnmente como s ↝ t . Intuitivamente, una secuencia de pasos de reducción t ₁ ↝ t ₂ ↝ ... ↝ t _n puede considerarse como una secuencia de pasos de reescritura t ₁ → t ₂ → ... → t _n , pero con el término inicial t ₁ siendo instanciados cada vez más, según sea necesario para que cada una de las reglas utilizadas sea aplicable.

El ejemplo anterior de cálculo de paramodulación corresponde a la siguiente secuencia de estrechamiento ("↓" indica creación de instancias aquí):

El último término, v ₂ . v2 ._​ nil se puede unificar sintácticamente con el término original del lado derecho a . a . nulo .

El lema de estrechamiento ^[39] asegura que siempre que una instancia de un término s pueda reescribirse en un término t mediante un sistema de reescritura de términos convergente, entonces s y t pueden reducirse y reescribirse en un término s ′ y t ′ , respectivamente, tales que t ′ es una instancia de s ′ .

Formalmente: siempre que sσ →∗ t es válido para alguna sustitución σ, entonces existen términos s ′ , t ′ tales que s ↝∗ s ′ y t →∗ t ′ y s ′ τ = t ′ para alguna sustitución τ.

Unificación de orden superior

En la reducción de Goldfarb ^{[40] del} décimo problema de Hilbert a unificabilidad de segundo orden, la ecuación corresponde al problema de unificación representado, con variables funcionales correspondientes a y fresco . ${\displaystyle X_{1}*X_{2}=X_{3}}$ ${\displaystyle F_{i}}$ ${\displaystyle X_{i}}$ ${\displaystyle G}$

Muchas aplicaciones requieren que se considere la unificación de términos lambda tipificados en lugar de términos de primer orden. Esta unificación suele denominarse unificación de orden superior . La unificación de orden superior es indecidible , ^{[40] [41] [42]} y tales problemas de unificación no tienen la mayoría de los unificadores generales. Por ejemplo, el problema de unificación { f ( a , b , a ) ≐ d ( b , a , c ) }, donde la única variable es f , tiene las soluciones { f ↦ λ x .λ y .λ z . d ( y , x , c ) }, { f ↦ λ x .λ y .λ z . re ( y , z , c ) }, { f ↦ λ x .λ y .λ z . d ( y , a , c ) }, { f ↦ λ x .λ y .λ z . re ( segundo , x , c ) }, { f ↦ λ x .λ y .λ z . d ( b , z , c ) } y { f ↦ λ x .λ y .λ z . re ( b , a , c ) }. Una rama bien estudiada de la unificación de orden superior es el problema de unificar términos lambda simplemente tipados módulo la igualdad determinada por conversiones αβη. Gérard Huet dio un algoritmo de (pre)unificación semidecidible ^[43] que permite una búsqueda sistemática del espacio de unificadores (generalizando el algoritmo de unificación de Martelli-Montanari ^[5] con reglas para términos que contienen variables de orden superior) que parece funcionar suficientemente bien en la práctica. Huet ^[44] y Gilles Dowek ^[45] han escrito artículos sobre este tema.

Varios subconjuntos de unificación de orden superior se comportan bien, ya que son decidibles y tienen un unificador más general para problemas solucionables. Uno de esos subconjuntos son los términos de primer orden descritos anteriormente. La unificación de patrones de orden superior , debida a Dale Miller, ^[46] es otro de esos subconjuntos. Los lenguajes de programación lógica de orden superior λProlog y Twelf han pasado de una unificación completa de orden superior a implementar solo el fragmento de patrón; Sorprendentemente, la unificación de patrones es suficiente para casi todos los programas, si cada problema de unificación que no es de patrón se suspende hasta que una sustitución posterior coloque la unificación en el fragmento de patrón. Un superconjunto de unificación de patrones llamado unificación de funciones como constructores también se comporta bien. ^[47] El demostrador del teorema de Zipperposition tiene un algoritmo que integra estos subconjuntos de buen comportamiento en un algoritmo completo de unificación de orden superior. ^[2]

En lingüística computacional, una de las teorías más influyentes de la construcción elíptica es que las elipses están representadas por variables libres cuyos valores luego se determinan mediante unificación de orden superior. Por ejemplo, la representación semántica de "A Jon le gusta Mary y a Peter también" es como ( j , m ) ∧ R( p ) y el valor de R (la representación semántica de la elipsis) está determinado por la ecuación como ( j , m ) = R( j ) . El proceso de resolución de tales ecuaciones se llama unificación de orden superior. ^[48]

Wayne Snyder dio una generalización tanto de la unificación de orden superior como de la unificación E, es decir, un algoritmo para unificar términos lambda módulo una teoría ecuacional. ^[49]

Ver también

• Reescritura
• Regla admisible
• Sustitución explícita en cálculo lambda
• Resolución de ecuaciones matemáticas
• Desunificación : resolviendo inecuaciones entre expresiones simbólicas
• Antiunificación : calcular una generalización mínima general (lgg) de dos términos, dual para calcular una instancia más general (mgu)
• Red de subsunción , una red que tiene la unificación como encuentro y la antiunificación como unión
• Alineación de ontologías (usar unificación con equivalencia semántica )

Notas

1. Por ejemplo, a ⊕ ( b ⊕ f ( x )) ≡ a ⊕ ( f ( x ) ⊕ b ) ≡ ( b ⊕ f ( x )) ⊕ a ≡ ( f ( x ) ⊕ b ) ⊕ a
2. desde ${\displaystyle (x\oplus y)\{x\mapsto z,y\mapsto z\}=z\oplus z\equiv z}$
3. ya que z { z ↦ x ⊕ y } = x ⊕ y
4. formalmente: cada unificador τ satisface ∀ x : xτ = ( xσ ) ρ para alguna sustitución ρ
5. Robinson utilizó la unificación sintáctica de primer orden como componente básico de su procedimiento de resolución para la lógica de primer orden, un gran paso adelante en la tecnología de razonamiento automatizado , ya que eliminó una fuente de explosión combinatoria : la búsqueda de instancias de términos. ^[14]
6. El descubrimiento independiente se indica en Martelli y Montanari (1982), sección 1, p.259. El editor de la revista recibió Paterson & Wegman (1978) en septiembre de 1976.
7. Alg.1, p.261. Su regla (a) corresponde al intercambio de reglas aquí, (b) eliminar , (c) descomponer y entrar en conflicto , y ( d) eliminar y verificar .
8. Aunque la regla mantiene x ≐ t en G , no puede repetirse para siempre ya que su condición previa x ∈ vars ( G ) queda invalidada por su primera aplicación. De manera más general, se garantiza que el algoritmo terminará siempre, ver más abajo.
9. en presencia de la igualdad C , las igualdades N _l y N _r son equivalentes, similares para D _l y D _r

Referencias

1. Dowek, Gilles (1 de enero de 2001). "Unificación y emparejamiento de orden superior". Manual de razonamiento automatizado. Elsevier Science Publishers BV págs. 1009–1062. ISBN 978-0-444-50812-6. Archivado desde el original el 15 de mayo de 2019 . Consultado el 15 de mayo de 2019 .
2. Vukmirović, Petar; Bentkamp, ​​Alejandro; Nummelin, Visa (14 de diciembre de 2021). "Unificación eficiente y completa de orden superior". Métodos lógicos en informática . 17 (4): 6919. arXiv : 2011.09507 . doi : 10.46298/lmcs-17(4:18)2021 .
3. Apto, Krzysztof R. (1997). De la programación lógica a Prolog (1. ed. publicada). Londres Múnich: Prentice Hall. pag. 24.ISBN​ 013230368X.
4. Fages, François; Huet, Gerard (1986). "Conjuntos completos de unificadores y emparejadores en teorías ecuacionales". Informática Teórica . 43 : 189-200. doi : 10.1016/0304-3975(86)90175-1 .
5. Martelli, Alberto; Montanari, Ugo (abril de 1982). "Un algoritmo de unificación eficiente". Transmisión ACM. Programa. Lang. Sistema . 4 (2): 258–282. doi :10.1145/357162.357169. S2CID  10921306.
6. Robinson (1965) n.º 2.5, 2.14, p.25
7. Robinson (1965) n.º 5.6, p.32
8. Robinson (1965) n.º 5.8, p.32
9. J. Herbrand: Investigaciones sobre la teoría de la demostración. Travaux de la société des Sciences et des Lettres de Varsovie , Clase III, Sciences Mathématiques et Physiques, 33, 1930.
10. Jacques Herbrand (1930). Investigaciones sobre la teoría de la demostración (PDF) (tesis doctoral). A. vol. 1252. Universidad de París.Aquí: p.96-97
11. Claus-Peter Wirth; Jörg Siekmann; Christoph Benzmüller; Serge Autexier (2009). Conferencias sobre Jacques Herbrand como lógico (Informe SEKI). DFKI. arXiv : 0902.4682 .Aquí: p.56
12. Robinson, JA (enero de 1965). "Una lógica orientada a máquinas basada en el principio de resolución". Revista de la ACM . 12 (1): 23–41. doi : 10.1145/321250.321253 . S2CID  14389185.; Aquí: sección 5.8, p.32
13. JA Robinson (1971). "Lógica computacional: el cálculo de unificación". Inteligencia de las máquinas . 6 : 63–72.
14. David A. Duffy (1991). Principios de la demostración automatizada de teoremas . Nueva York: Wiley. ISBN 0-471-92784-8.Aquí: Introducción de la sección 3.3.3 "Unificación" , p.72.
15. de Champeaux, Dennis (agosto de 2022). "Algoritmo de unificación lineal más rápido" (PDF) . Revista de razonamiento automatizado . 66 : 845–860. doi :10.1007/s10817-022-09635-1.
16. Por Martelli y Montanari (1982):
    • Lewis Denver Baxter (febrero de 1976). Un algoritmo de unificación prácticamente lineal (PDF) (Informe Res.). vol. CS-76-13. Univ. de Waterloo, Ontario.
    • Gérard Huet (septiembre de 1976). Resolución de ecuaciones en idiomas de orden 1,2,...ω (Estos estados). Universidad de París VII.
    • Martelli, Alberto y Montanari, Ugo (julio de 1976). Unificación en tiempo y espacio lineal: una presentación estructurada (Nota interna). vol. IEI-B76-16. Consiglio Nazionale delle Ricerche, Pisa. Archivado desde el original el 15 de enero de 2015.
    • Paterson, MS; Wegman, MN (mayo de 1976). Chandra, Ashok K.; Wotschke, Detlef; Friedman, Emily P.; Harrison, Michael A. (eds.). Unificación lineal . Actas del octavo Simposio anual ACM sobre Teoría de la Computación (STOC). ACM. págs. 181–186. doi : 10.1145/800113.803646 .
    • Paterson, MS ; Wegman, MN (abril de 1978). "Unificación lineal". J. Computación. Sistema. Ciencia . 16 (2): 158–167. doi : 10.1016/0022-0000(78)90043-0 .
    • JA Robinson (enero de 1976). "Unificación rápida". En Woodrow W. Bledsoe , Michael M. Richter (ed.). Proc. Taller de demostración de teoremas en Oberwolfach . Informe del taller de Oberwolfach. vol. 1976/3.^{[ enlace muerto permanente ]}
    • M. Venturini-Zilli (octubre de 1975). "Complejidad del algoritmo de unificación de expresiones de primer orden". Calcolo . 12 (4): 361–372. doi :10.1007/BF02575754. S2CID  189789152.
17. Baader, Franz; Snyder, Wayne (2001). "Teoría de la Unificación" (PDF) . Manual de razonamiento automatizado . págs. 445–533. doi :10.1016/B978-044450813-3/50010-2.
18. McBride, Conor (octubre de 2003). "Unificación de primer orden por recursión estructural". Revista de programación funcional . 13 (6): 1061–1076. CiteSeerX 10.1.1.25.1516 . doi :10.1017/S0956796803004957. ISSN  0956-7968. S2CID  43523380 . Consultado el 30 de marzo de 2012 . 
19. por ejemplo, Paterson y Wegman (1978), sección 2, p.159
20. "Aritmética declarativa de enteros". SWI-Prólogo . Consultado el 18 de febrero de 2024 .
21. Jonathan Calder, Mike Reape y Hank Zeevat, Un algoritmo de generación en gramática categorial de unificación. En Actas de la 4ª Conferencia del Capítulo Europeo de la Asociación de Lingüística Computacional, páginas 233-240, Manchester, Inglaterra (10-12 de abril), Instituto de Ciencia y Tecnología de la Universidad de Manchester, 1989.
22. Graeme Hirst y David St-Onge, [1] Cadenas léxicas como representaciones de contexto para la detección y corrección de malapropismos, 1998.
23. Walther, Christoph (1985). "Una solución mecánica de la apisonadora de Schubert mediante resoluciones variadas" (PDF) . Artif. Intel . 26 (2): 217–224. doi :10.1016/0004-3702(85)90029-3. Archivado desde el original (PDF) el 8 de julio de 2011 . Consultado el 28 de junio de 2013 .
24. Smolka, Gert (noviembre de 1988). Programación lógica con tipos ordenados polimórficamente (PDF) . En t. Taller de Programación Algebraica y Lógica. LNCS. vol. 343. Saltador. págs. 53–70. doi :10.1007/3-540-50667-5_58.
25. Schmidt-Schauß, Manfred (abril de 1988). Aspectos computacionales de una lógica ordenada por orden con declaraciones de términos . Apuntes de conferencias sobre inteligencia artificial (LNAI). vol. 395. Saltador.
26. Gordon D. Plotkin , Propiedades teóricas de subsunción de celosía , Memorando MIP-R-77, Univ. Edimburgo, junio de 1970
27. Mark E. Stickel , Un algoritmo de unificación para funciones asociativas-conmutativas , Revista de la Asociación de Maquinaria de Computación, vol.28, no.3, págs. 423–434, 1981
28. F. Fages, Unificación asociativo-conmutativa , J. Symbolic Comput., vol.3, no.3, págs. 257-275, 1987
29. Franz Baader, La unificación en semigrupos idempotentes es de tipo cero , J. Automat. Razonamiento, vol.2, no.3, 1986
30. J. Makanin, El problema de la solubilidad de ecuaciones en un semigrupo libre , Akad. Nauk SSSR, vol.233, no.2, 1977
31. F. Fages (1987). «Unificación asociativo-conmutativa» (PDF) . J. Computación simbólica . 3 (3): 257–275. doi :10.1016/s0747-7171(87)80004-4. S2CID  40499266.
32. Martín, U., Nipkow, T. (1986). "Unificación en anillos booleanos". En Jörg H. Siekmann (ed.). Proc. 8º CADE . LNCS. vol. 230. Saltador. págs. 506–513.{{cite book}}: CS1 maint: multiple names: authors list (link)
33. A. Boudet; JP Jouannaud; M. Schmidt-Schauß (1989). "Unificación de anillos booleanos y grupos abelianos". Revista de Computación Simbólica . 8 (5): 449–477. doi : 10.1016/s0747-7171(89)80054-9 .
34. Baader y Snyder (2001), pág. 486.
35. F. Baader y S. Ghilardi, Unificación en lógicas modales y de descripción , Logic Journal of the IGPL 19 (2011), no. 6, págs. 705–730.
36. P. Szabo, Unifikationstheorie erster Ordnung ( Teoría de la unificación de primer orden ), Tesis, Univ. Karlsruhe, Alemania Occidental, 1982
37. Jörg H. Siekmann, Unificación universal , Proc. 7° Int. Conf. sobre deducción automatizada, Springer LNCS vol.170, págs. 1–42, 1984
38. N. Dershowitz y G. Sivakumar, Resolución de objetivos en lenguajes ecuacionales , Proc. 1º Int. Taller sobre sistemas de reescritura de términos condicionales, Springer LNCS vol.308, págs. 45–55, 1988
39. Hada (1979). "Unificación de primer orden en una teoría ecuacional". Proc. IV Taller de Deducción Automatizada . págs. 161-167.
40. Warren D. Goldfarb (1981). "La indecidibilidad del problema de la unificación de segundo orden". TCS . 13 (2): 225–230. doi : 10.1016/0304-3975(81)90040-2 .
41. Gérard P. Huet (1973). "La indecidibilidad de la unificación en la lógica de tercer orden". Información y Control . 22 (3): 257–267. doi : 10.1016/S0019-9958(73)90301-X .
42. Claudio Lucchesi: La indecidibilidad del problema de la unificación de las lenguas de tercer orden (Informe de investigación CSRR 2059; Departamento de Ciencias de la Computación, Universidad de Waterloo, 1972)
43. Gérard Huet: un algoritmo de unificación para cálculo Lambda mecanografiado []
44. Gérard Huet: Unificación de orden superior 30 años después
45. Gilles Dowek: unificación y emparejamiento de orden superior. Manual de razonamiento automatizado 2001: 1009–1062
46. Molinero, Dale (1991). "Un lenguaje de programación lógica con abstracción Lambda, variables de función y unificación simple" (PDF) . Revista de Lógica y Computación . 1 (4): 497–536. doi : 10.1093/logcom/1.4.497.
47. Libal, Tomer; Miller, Dale (mayo de 2022). "Unificación de orden superior de funciones como constructores: unificación de patrones extendidos". Anales de Matemáticas e Inteligencia Artificial . 90 (5): 455–479. doi : 10.1007/s10472-021-09774-y .
48. Gardent, Claire ; Kohlhase, Michael ; Konrad, Karsten (1997). "Un enfoque de unificación de orden superior y multinivel para la elipsis". Presentado a la Asociación Europea de Lingüística Computacional (EACL) . CiteSeerX 10.1.1.55.9018 . 
49. Wayne Snyder (julio de 1990). "E-unificación de orden superior". Proc. X Jornadas de Deducción Automatizada . LNAI. vol. 449. Saltador. págs. 573–587.

Otras lecturas

• Franz Baader y Wayne Snyder (2001). «Teoría de la Unificación» Archivado el 8 de junio de 2015 en Wayback Machine . En John Alan Robinson y Andrei Voronkov , editores, Handbook of Automated Reasoning , volumen I, páginas 447–533. Editores científicos de Elsevier. ^{[ enlace muerto ]}
• Gilles Dowek (2001). «Unificación y emparejamiento de orden superior» Archivado el 15 de mayo de 2019 en Wayback Machine . En Manual de razonamiento automatizado .
• Franz Baader y Tobias Nipkow (1998). Reescritura de términos y todo eso. Prensa de la Universidad de Cambridge.
• Franz Baader y Jörg H. Siekmann  [Delaware] (1993). "Teoría de la unificación". En Manual de Lógica en Inteligencia Artificial y Programación Lógica .
• Jean-Pierre Jouannaud y Claude Kirchner (1991). "Resolución de ecuaciones en álgebras abstractas: un estudio de unificación basado en reglas". En Lógica Computacional: Ensayos en Honor a Alan Robinson .
• Nachum Dershowitz y Jean-Pierre Jouannaud , Rewrite Systems , en: Jan van Leeuwen (ed.), Handbook of Theoretical Computer Science , volumen B, Modelos formales y semántica , Elsevier, 1990, págs. 243–320
• Jörg H. Siekmann (1990). "Teoría de la unificación". En Claude Kirchner (editor) Unificación . Prensa académica.
• Kevin Knight (marzo de 1989). "Unificación: una encuesta multidisciplinaria" (PDF) . Encuestas de Computación ACM . 21 (1): 93-124. CiteSeerX  10.1.1.64.8967 . doi :10.1145/62029.62030. S2CID  14619034.
• Gérard Huet y Derek C. Oppen (1980). "Ecuaciones y reglas de reescritura: una encuesta". Reporte técnico. Universidad Stanford.
• Raulefs, Peter; Siekmann, Jörg; Szabó, P.; Unvericht, E. (1979). "Un breve repaso sobre el estado del arte en problemas de emparejamiento y unificación". Boletín ACM SIGSAM . 13 (2): 14-20. doi :10.1145/1089208.1089210. S2CID  17033087.
• Claude Kirchner y Hélène Kirchner. Reescribir, resolver, demostrar . En la preparación de.