Unificación (informática)

Proceso algorítmico de resolución de ecuaciones

En lógica y ciencias de la computación , específicamente en razonamiento automatizado , 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, utilizando x , y , z como variables y tomando f como una función no interpretada , el conjunto de ecuaciones singleton { f (1, y ) = f ( x ,2)} es un problema de unificación sintáctica de primer orden que tiene la sustitución { x ↦ 1, y ↦ 2} como su única solución.

Las convenciones difieren en cuanto a qué valores pueden asumir las variables y qué expresiones se consideran equivalentes. En la unificación sintáctica de primer orden, las variables abarcan términos de primer orden y la equivalencia es sintáctica. Esta versión de unificación tiene una única "mejor" respuesta y se utiliza en la programación lógica y en la implementación de sistemas de tipos de lenguajes de programación , especialmente en algoritmos de inferencia de tipos basados ​​en Hindley-Milner . En la unificación de orden superior, posiblemente restringida a la unificación de patrones de orden superior , los términos pueden incluir expresiones lambda y la equivalencia depende de la reducción beta. Esta versión se utiliza en asistentes de prueba y programación lógica de orden superior, por ejemplo Isabelle , Twelf y lambdaProlog . Finalmente, en la unificación semántica o E-unificación, la igualdad está sujeta a conocimientos previos y las variables abarcan una variedad de dominios. Esta versión se utiliza en solucionadores SMT , algoritmos de reescritura de términos y análisis de protocolos criptográficos .

Definición 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 permite que aparezcan en un conjunto de ecuaciones o problema de unificación, y qué expresiones se consideran iguales, se distinguen varios marcos de unificación. Si se permiten variables de orden superior, es decir, variables que representan funciones , en una expresión, el proceso se denomina unificación de orden superior , en caso 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 denomina unificación sintáctica o libre , en caso contrario unificación semántica o ecuacional , o E-unificación , o teoría de unificación módulo . ${\displaystyle T}$

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

Prerrequisitos

Formalmente, un enfoque de unificación presupone

• Un conjunto infinito de variables . Para una unificación de orden superior, es conveniente elegir variables disjuntas del conjunto de variables ligadas al término lambda . ${\displaystyle V}$ ${\displaystyle V}$
• Un conjunto de términos tales que . Para la unificación de primer orden, es generalmente el conjunto de términos de primer orden (términos construidos a partir de símbolos de variables y funciones). Para 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}$
• Una asignación , que asigna a cada término el conjunto de variables libres que ocurren en . ${\displaystyle {\text{vars}}\colon 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 de fondo sobre ciertos símbolos de función; por ejemplo, si se considera conmutativo, si resulta de intercambiando los argumentos de en algunas ocurrencias (posiblemente todas). ^{[nota 1]} En el caso más típico de que no haya ningún conocimiento de fondo, entonces solo literalmente, 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 de fondo, está vacío), teoría de funciones no interpretadas (porque la unificación se realiza sobre términos no interpretados ), o teoría de constructores (porque todos los símbolos de función solo construyen términos de datos, en lugar de operar sobre ellos). Para la unificación de orden superior, generalmente si y son alfa equivalentes . ${\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 afectan al 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 la única solución { 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 de unificación sintáctica de segundo orden, ya que y es una variable de función. Una solución es { x ↦ a , y ↦ ( función identidad ) }; otra es { y ↦ ( función constante que asigna cada valor a a ), x ↦ ( cualquier valor ) }.

Sustitución

Una sustitución es una aplicación de variables a términos; la notación se refiere a una sustitución que asigna cada variable al término , para , y cada otra variable a sí misma; deben ser distintos por pares. La aplicación de esa sustitución a un término se escribe en notación de posfijo como ; significa (simultáneamente) reemplazar cada ocurrencia de cada variable en el término por . El resultado de aplicar una sustitución a un término se llama una instancia de ese término . Como un ejemplo de primer orden, aplicar 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 para alguna sustitución , entonces se dice que es más general que , y se dice que es más especial que, o está subsumido por, . Por ejemplo, es más general que si ⊕ es conmutativo , ya que 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 solo si ambos términos difieren solo en sus nombres de variable, no en su estructura sintáctica; tales términos se llaman variantes o renombramientos entre sí. Por ejemplo, es una variante de , ya que y Sin embargo, no es una variante de , ya que ninguna sustitución puede transformar el último término en el primero. El último término es, por lo tanto, propiamente más especial que el primero. ${\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}).}$$ ${\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 tengan una estructura diferente. ${\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 que, o está subsumida por, una sustitución si está subsumida por para cada término . También decimos que es más general que . De manera más formal, tomemos un conjunto infinito no vacío de variables auxiliares de modo que ninguna ecuación en el problema de unificación contenga variables de . Entonces, una sustitución está subsumida por otra sustitución si hay una sustitución tal que para todos los términos , . ^[2] Por ejemplo, está subsumida por , usando , pero no está subsumida 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 . Dicha 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 denomina 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 de orden superior sin restricciones) 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 denomina 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 infinito de miembros, o puede no existir en absoluto debido a una cadena infinita de miembros redundantes. ^[4] Por lo tanto, en general, los algoritmos de unificación calculan una aproximación finita del conjunto completo, que puede ser mínimo o no, aunque la mayoría de los algoritmos evitan los 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 único unificador que por sí mismo forma un conjunto de sustitución completo y mínimo, llamado el unificador más general .

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

Diagrama esquemático de triángulos que unifican sintácticamente los términos 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 ampliamente 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 llama el 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 el mgu, es decir, l ₁ σ = r ₁ σ ∧ ... ∧ l _n σ = r _n σ . Cualquier unificador del problema es subsumido ^{[nota 4]} por el mgu σ . La mgu es única hasta variantes: si S ₁ y S ₂ son ambos conjuntos de soluciones completas y mínimas 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 aparece 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 una 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 se ordenan de tal manera que las variables preceden a los símbolos de función. Los términos se ordenan de acuerdo con su longitud escrita creciente; 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ás pequeño en el que dos términos miembros de T difieren. Su conjunto de desacuerdo es el conjunto de subtérminos que comienzan en p , formalmente: { t | p  : ${\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 (cf. recuadro). ^{[12] [13] [nota 5]} El algoritmo de Robinson tenía un comportamiento exponencial en el peor de los casos tanto en el tiempo como en el espacio. ^{[11] [15]} Numerosos autores han propuesto algoritmos de unificación más eficientes. ^[16] Los algoritmos con comportamiento lineal en el peor de los casos fueron descubiertos independientemente por Martelli y Montanari (1976) y Paterson y Wegman (1976) ^{[nota 6]} Baader y Snyder (2001) utilizan una técnica similar a Paterson-Wegman, por lo tanto es lineal, ^[17] pero como la mayoría de los algoritmos de unificación en tiempo lineal es más lento que la versión de Robinson en entradas de tamaño pequeño debido a la sobrecarga de preprocesar las entradas y posprocesar la salida, como la construcción de una representación DAG . El algoritmo de de Champeaux (2022) también tiene una complejidad lineal en cuanto al tamaño de entrada, pero es competitivo con el algoritmo de Robinson en entradas de tamaño pequeño. La aceleración se obtiene mediante el uso de una representación orientada a objetos del cálculo de predicados que evita la necesidad de preprocesamiento y posprocesamiento, y en su lugar hace que los objetos variables sean responsables de crear una sustitución y de lidiar con el aliasing. De Champeaux afirma que la capacidad de agregar funcionalidad al cálculo de predicados representado como objetos programáticos también brinda oportunidades para optimizar otras operaciones lógicas. ^[15]

El siguiente algoritmo es de uso común y tiene su origen 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 ninguna de las x _i . Un conjunto de esta forma puede leerse como una sustitución. Si no hay solución, el algoritmo termina con ⊥; otros autores usan "Ω" o " fail " en ese caso. La operación de sustituir todas las ocurrencias de la variable x en el problema G con el término t se denota G { x ↦ t }. Para simplificar, los símbolos de constantes se consideran símbolos de función que tienen cero argumentos. ${\displaystyle G=\{s_{1}\doteq t_{1},...,s_{n}\doteq t_{n}\}}$

Se produce una comprobación

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 aparecería como un subtérmino de sí mismo. En el conjunto de términos de primer orden (finitos) como se definió anteriormente, la ecuación x ≐ f (..., x , ...) no tiene solución; por lo tanto, la regla de eliminación solo se puede aplicar si x ∉ vars ( t ). Dado que esa verificación adicional, llamada happen check , 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 terminación

Para la prueba de terminación del algoritmo, considere una tripleta 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 los lados izquierdos de ecuaciones potenciales, y n _eqn es el número de ecuaciones. Cuando se aplica la regla delete , 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 puede aumentar n _var nuevamente. Cuando se aplica la regla decompose , conflict o swap , 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 delete o check no puede aumentar n _lhs , pero disminuye n _eqn . Por lo tanto, cualquier aplicación de regla disminuye la tripleta con respecto al orden lexicográfico , lo que es posible solo 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 tipos dependientes 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 para su instancia menos común. Su representación dag (parte naranja más a la derecha) sigue siendo de 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 ⁠ ⁠ ${\displaystyle (((a*z)*y)*x)*w\doteq w*(x*(y*(z*a)))}$ tiene el unificador más general ⁠ ⁠ ${\displaystyle \{z\mapsto a,y\mapsto a*a,x\mapsto (a*a)*(a*a),w\mapsto ((a*a)*(a*a))*((a*a)*(a*a))\}}$ , véase la 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]

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 . En concreto, la unificación es un elemento básico de la resolución , una regla de inferencia para determinar la satisfacibilidad de una fórmula. En Prolog , el símbolo de igualdad =implica una unificación sintáctica de primer orden. Representa el mecanismo de vinculación de los contenidos de las variables y puede considerarse como una especie de asignación única.

En Prolog:

1. Una variable se puede unificar con una constante, un término u otra variable, convirtiéndose así en su alias. En muchos dialectos modernos de Prolog y en lógica de primer orden , una variable no se puede unificar con un término que la contenga; esto es lo que se denomina la comprobación de ocurrencia .
2. Dos constantes sólo pueden unificarse si son idénticas.
3. De manera similar, un término puede unificarse 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 pueden unificarse simultáneamente. Tenga en cuenta que se trata de un comportamiento recursivo.
4. La mayoría de las operaciones, incluidas +, -, *, /, no se evalúan con =. Por lo tanto, por ejemplo, 1+2 = 3no es satisfacible porque son sintácticamente diferentes. El uso de restricciones aritméticas de números enteros #=introduce una forma de E-unificación para la cual se interpretan y evalúan estas operaciones. ^[20]

Aplicación: inferencia de tipos

Los algoritmos de inferencia de tipos se basan normalmente en la unificación, en particular la inferencia de tipos Hindley-Milner , que utilizan los lenguajes funcionales Haskell y ML . Por ejemplo, al intentar inferir el tipo de la expresión Haskell True : ['x'], el compilador utilizará el tipo a -> [a] -> [a]de la función de construcción de listas (:), el tipo Booldel primer argumento Truey el tipo [Char]del segundo argumento ['x']. La variable de tipo polimórfica ase unificará con Booly el segundo argumento [a]se unificará con [Char]. ano pueden ser ambos Booly Charal mismo tiempo, por lo tanto, esta expresión no está tipificada correctamente.

Al igual que para 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 instancia en esa expresión. Una teoría específica podría restringir esta regla con una comprobación de ocurrencia.
2. Dos constantes de tipo se unifican solo si son del mismo tipo.
3. Dos construcciones de tipos se unifican solo si son aplicaciones del mismo constructor de tipos y todos sus tipos de componentes se unifican recursivamente.

Aplicación: Unificación de la 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 ordenada por orden permite asignar untipo a cada término y declarar un tipo s ₁ como un subtipo de otro tipo s ₂ , comúnmente escrito como s ₁ ⊆ s _{2 . Por ejemplo,} cuando se razona sobre criaturas biológicas, es útil declarar que un tipo perro es un subtipo de un tipo animal . Siempre que se requieraun término de algún tipo s , se puede proporcionar en su lugar un término de cualquier subtipo de s . Por ejemplo, suponiendo una declaración de función mother : animal → animal , y una declaración de constante lassie : dog , el término mother ( 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 puede emitir otra declaración mother : dog → dog ; esto se llama sobrecarga de funciones , similar a la sobrecarga en lenguajes de programación .

Walther dio un algoritmo de unificación para términos en lógica ordenada, requiriendo que para cualesquiera dos ordenaciones declaradas s ₁ , s ₂ su intersección s ₁ ∩ s ₂ también se declare: si x ₁ y x ₂ son variables de orden 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, reduciéndolo así a un orden de magnitud, ya que muchos predicados unarios se convirtieron en ordenaciones.

Smolka generalizó la lógica de ordenación ordenada para permitir el polimorfismo paramétrico . ^[24] En su marco, las declaraciones de subclasificación se propagan a expresiones de tipo complejas. 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 se infiere automáticamente la relación list ( int ) ⊆ list ( float ), lo que significa que cada lista de números enteros es también una lista de números flotantes.

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

Unificación de términos infinitos

Antecedentes sobre los árboles infinitos:

• B. Courcelle (1983). "Propiedades fundamentales de los árboles infinitos". Theoret. Comput. Sci . 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 3rd Annual Symp. on Logic in Computer Science, Edimburgo , pp. 348–357.
• Joxan Jaffar; Peter J. Stuckey (1986). "Semántica de la programación lógica de árboles infinitos". Ciencias de la computación 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.). Prolog y árboles infinitos . Academic Press.
• Alain Colmerauer (1984). "Ecuaciones e inecuaciones en árboles finitos e infinitos". En ICOT (ed.). Proc. Int. Conf. on Fifth Generation Computer Systems . págs. 85–99.

Aplicaciones:

• Francis Giannesini; Jacques Cohen (1984). "Generación de analizadores sintácticos y manipulación gramatical utilizando los árboles infinitos de Prolog". Journal of Logic Programming . 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 un cierto conocimiento ecuacional previo 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 E-unificación ); para otros, se ha demostrado que no pueden existir tales algoritmos.

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

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

Conjuntos de conocimientos previos específicos E

Se dice que la unificación es decidible para una teoría si se ha ideado un algoritmo de unificación que termina para cualquier problema de entrada solucionable , pero que puede seguir buscando eternamente soluciones para un problema de entrada irresoluble.

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

• A ^[26]
• A , C ^[27]
• A , C , yo ^[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 con símbolos adicionales arbitrarios (pero no axiomas) ^[34]
• Álgebras modales de K4 ^[35]

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

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

Paramodulación unilateral

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

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

Por ejemplo, se utiliza un sistema de reescritura de términos R que define el operador de adición de listas construidas a partir de cons y nil ; donde cons ( x , y ) se escribe en notación infija como x . y para abreviar; p. ej., app ( a . b . nil , c . d . nil ) → a . app ( b . nil , c . d . nil ) → a . b . app ( nil , c . d . nil ) → a . b . c . d . nil demuestra la concatenación de las listas a . b . nil y c . d . nil , empleando las reglas de reescritura 2,2 y 1. La teoría ecuacional E correspondiente a R es el cierre de congruencia de R , ambas vistas como relaciones binarias en términos. Por ejemplo, app ( a . b . nil , c . d . nil ) ≡ a . b . c . d . nil ≡ app ( a . b . c . d . nil , nil ). El algoritmo de paramodulación enumera soluciones a ecuaciones con respecto a esa E cuando se alimenta con el ejemplo R .

A continuación se muestra un ejemplo exitoso de ruta de cálculo para el problema de unificación { app ( x , app ( y , x )) ≐ a . a . nil }. Para evitar conflictos de nombres de variables, las reglas de reescritura se renombran consistentemente cada vez antes de su uso mediante la regla mutate ; v ₂ , v ₃ , ... son nombres de variables generados por computadora para este propósito. En cada línea, la ecuación elegida de G se resalta en rojo. Cada vez que se aplica la regla mutate , la regla de reescritura elegida ( 1 o 2 ) se indica entre paréntesis. Desde la última línea, se puede obtener la sustitución unificadora S = { y ↦ nil , x ↦ a . nil } . De hecho, app ( x , app ( y , x )) { y ↦ nil , x ↦ a . nil } = app ( a . nil , app ( nil , a . nil )) ≡ app ( a . nil , a . nil ) ≡ a . app ( nil , a . nil ) ≡ a . a . nil resuelve el problema dado. Una segunda ruta de cálculo exitosa, obtenible eligiendo "mutate(1), mutate(2), mutate(2), mutate(1)" conduce a la sustitución S = { y ↦ a . a . nil , x ↦ nil }; no se muestra aquí. Ninguna otra ruta 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), utilizando una regla de reescritura l → r (fila superior)

Si R es un sistema de reescritura de términos convergentes para E , una alternativa a la sección anterior consiste en la aplicación sucesiva de " pasos de reducción "; esto eventualmente enumerará todas las soluciones de una ecuación dada. Un paso de reducción (cf. figura) consiste en

• eligiendo 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 del 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 estrechamiento 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 instanciado cada vez más, según sea necesario para hacer aplicable cada una de las reglas utilizadas.

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

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

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 estrecharse y reescribirse en un término s ′ y t ′ , respectivamente, de modo que t ′ sea una instancia de s ′ .

Formalmente: siempre que sσ →∗ t se cumple 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 la unificabilidad de segundo orden, la ecuación corresponde al problema de unificación representado, con variables de función correspondientes a y fresh . ${\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 tipados en lugar de términos de primer orden. Dicha unificación a menudo se denomina unificación de orden superior . La unificación de orden superior es indecidible , ^{[40] [41] [42]} y dichos 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 . d ( y , z , c ) }, { f ↦ λ x .λ y .λ z . d ( y , a , c ) }, { f ↦ λ x .λ y .λ z . d ( b , x , c ) }, { f ↦ λ x .λ y .λ z . d ( b , z , c ) } y { f ↦ λ x .λ y .λ z . d ( 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 las 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 que analizan este tema.

Varios subconjuntos de unificación de orden superior se comportan bien, en el sentido de que son decidibles y tienen un unificador más general para problemas solucionables. Uno de estos subconjuntos son los términos de primer orden descritos anteriormente. La unificación de patrones de orden superior , debido a Dale Miller, ^[46] es otro de estos subconjuntos. Los lenguajes de programación lógica de orden superior λProlog y Twelf han pasado de la unificación de orden superior completa 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 sea de patrones 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 de teoremas Zipperposition tiene un algoritmo que integra estos subconjuntos de buen comportamiento en un algoritmo de unificación de orden superior completo. ^[2]

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

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

Véase también

• Reescritura
• Regla admisible
• Sustitución explícita en el cálculo lambda
• Resolución de ecuaciones matemáticas
• Desunificación : solución de inecuaciones entre expresiones simbólicas
• Antiunificación : calcular una generalización menos 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 punto de encuentro y la antiunificación como punto de unión.
• Alineación de ontologías (utilizar 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 un elemento 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 menciona en Martelli & Montanari (1982), sección 1, pág. 259. El editor de la revista recibió Paterson & Wegman (1978) en septiembre de 1976.
7. Alg.1, p.261. Su regla (a) corresponde a la regla swap aquí, (b) a delete , (c) a ambos, descomponer y poner en conflicto , y (d) a ambos, eliminar y comprobar .
8. Aunque la regla mantiene x ≐ t en G , no puede repetirse indefinidamente ya que su condición previa x ∈ vars ( G ) queda invalidada por su primera aplicación. En términos más generales, se garantiza que el algoritmo terminará siempre, véase más abajo.
9. en presencia de 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-6Archivado desde el original el 15 de mayo de 2019 . Consultado el 15 de mayo de 2019 .
2. Vukmirović, Petar; Bentkamp, ​​Alexander; Nummelin, Visa (14 de diciembre de 2021). "Unificación eficiente de orden superior completo". Métodos lógicos en informática . 17 (4): 6919. arXiv : 2011.09507 . doi : 10.46298/lmcs-17(4:18)2021 .
3. Apt, Krzysztof R. (1997). De la programación lógica a Prolog (1.ª edición). Londres, Múnich: Prentice Hall. pág. 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". ACM Trans. Program. Lang. Syst . 4 (2): 258–282. doi :10.1145/357162.357169. S2CID  10921306.
6. Robinson (1965) nº 2.5, 2.14, pág. 25
7. Robinson (1965) nº 5.6, pág. 32
8. Robinson (1965) nº 5.8, pág. 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). Lecciones 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í: secc.5.8, p.32
13. JA Robinson (1971). "Lógica computacional: la computación de unificación". Inteligencia artificial . 6 : 63–72.
14. David A. Duffy (1991). Principios de la demostración automática de teoremas . Nueva York: Wiley. ISBN 0-471-92784-8.Aquí: Introducción de la sección 3.3.3 "Unificación" , pág. 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 de la 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 de la 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. Comput. Syst. Sci . 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 de Oberwolfach . Informe del taller de Oberwolfach. Vol. 1976/3.^{[ enlace muerto permanente ]}
    • M. Venturini-Zilli (octubre de 1975). "Complejidad del algoritmo de unificación para 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). "First-Order Unification by Structural Recursion". Journal of Functional Programming . 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ág. 159.
20. "Aritmética declarativa de enteros". SWI-Prolog . Consultado el 18 de febrero de 2024 .
21. Jonathan Calder, Mike Reape y Hank Zeevat, Un algoritmo para la generación de 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 del 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 resolución múltiple" (PDF) . Artif. Intell . 26 (2): 217–224. doi :10.1016/0004-3702(85)90029-3. Archivado desde el original (PDF) el 2011-07-08 . Consultado el 2013-06-28 .
24. Smolka, Gert (noviembre de 1988). Programación lógica con tipos ordenados polimórficamente (PDF) . Taller internacional sobre programación algebraica y lógica. LNCS. Vol. 343. Springer. 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 con declaraciones de términos . Apuntes de clase sobre inteligencia artificial (LNAI). Vol. 395. Springer.
26. Gordon D. Plotkin , Propiedades teóricas de la subsunción en red , Memorándum MIP-R-77, Univ. Edimburgo, junio de 1970
27. Mark E. Stickel , Un algoritmo de unificación para funciones asociativas-conmutativas , Journal of the Association for Computing Machinery, vol. 28, n.º 3, págs. 423-434, 1981
28. F. Fages, Unificación asociativa-conmutativa , J. Symbolic Comput., vol. 3, n.º 3, págs. 257-275, 1987
29. Franz Baader, La unificación en semigrupos idempotentes es de tipo cero , J. Automat. Reasoning, vol. 2, n.º 3, 1986
30. J. Makanin, El problema de la solubilidad de ecuaciones en un semigrupo libre , Akad. Nauk SSSR, vol. 233, n.º 2, 1977
31. F. Fages (1987). "Unificación asociativa-conmutativa" (PDF) . J. Symbolic Comput . 3 (3): 257–275. doi :10.1016/s0747-7171(87)80004-4. S2CID  40499266.
32. Martin, U., Nipkow, T. (1986). "Unificación en anillos booleanos". En Jörg H. Siekmann (ed.). Proc. 8th CADE . LNCS. Vol. 230. Springer. 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". Journal of Symbolic Computation . 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 descriptivas , 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 , Actas de la 7.ª conferencia internacional 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 , Actas del 1.er taller internacional sobre sistemas de reescritura de términos condicionales, Springer LNCS vol. 308, págs. 45-55, 1988
39. Fay (1979). "Unificación de primer orden en una teoría ecuacional". Actas del 4º Taller sobre deducción automatizada . págs. 161–167.
40. Warren D. Goldfarb (1981). "La indecidibilidad del problema de 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 unificación para lenguajes 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. Miller, Dale (1991). "Un lenguaje de programación lógica con abstracción Lambda, variables de función y unificación simple" (PDF) . Journal of Logic and Computation . 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 extendida". 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 niveles múltiples para la elipsis". Enviado a la Asociación Europea de Lingüística Computacional (EACL) . CiteSeerX 10.1.1.55.9018 . 
49. Wayne Snyder (julio de 1990). "Unificación electrónica de orden superior". Proc. 10th Conference on Automated Deduction . LNAI. Vol. 449. Springer. págs. 573–587.

Lectura adicional

• Franz Baader y Wayne Snyder (2001). "Unification Theory" 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. Elsevier Science Publishers. ^{[ enlace roto ]}
• Gilles Dowek (2001). "Unificación y emparejamiento de orden superior" Archivado el 15 de mayo de 2019 en Wayback Machine . En Handbook of Automated Reasoning .
• Franz Baader y Tobias Nipkow (1998). Term Rewriting and All That [Reescritura de términos y todo eso]. Cambridge University Press.
• Franz Baader y Jörg H. Siekmann  [de] (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 Formal Models and Semantics , Elsevier, 1990, págs. 243–320
• Jörg H. Siekmann (1990). "Teoría de la unificación". En Claude Kirchner (editor) Unificación . Academic Press.
• Kevin Knight (marzo de 1989). "Unificación: una encuesta multidisciplinaria" (PDF) . Encuestas de computación de la 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". Informe técnico. Universidad de Stanford.
• Raulefs, Peter; Siekmann, Jörg; Szabó, P.; Unvericht, E. (1979). "Un breve estudio 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 preparación.