Unificacion De Robinson

Capıtulo 1

Algoritmo de unificaci´n de Robinson o

´ 1.0 Introduccion
Con objeto de encontrar el unificador de m´xima generalidad de dos t´rminos a e se han propuesto numerosos algoritmos siendo el m´s conocido el de Robinson. a El algoritmo de unificaci´n de Robinson data del a˜o 1965. o n La claridad del m´todo utilizado por el algoritmo lo hace muy util, tanto e ´ desde un punto de vistadid´ctico como desde un punto de vista de implemena taci´n. o Vamos a exponer el m´todo en un cuadro general y posteriormente lo aplie caremos a varios ejemplos. Para la mejor comprensi´n del algoritmo damos unas nociones previas que o ser´n de utilidad. a

´ 1.1 Elementos para el algoritmo de unificacion
Entre los elementos que vamos a considerar se encuentran el llamado primer par dediscordancia entre dos t´rminos, y la aparici´n de variables dentro de un e o t´rmino occur check (comprobaci´n de apariciones). e o

1.1.0 Primer par de discordancia
Tomemos dos t´rminos que no sean iguales. Eso significa que habr´ alguna e a diferencia entre ellos. Esta diferencia puede hallarse en el nombre del funtor, en el n´mero de argumentos, o en alguno de los argumentos. u Si la diferencia est´en el nombre del funtor, el primer par de discordancia a es la pareja formada por los dos t´rminos. Si est´ en el n´mero de argumentos, e a u al igual que antes, el primer par de discordancia resulta ser el formado por los dos t´rminos considerados. e En cambio, si coinciden en los funtores y en el n´mero de argumentos, el u primer par de discordancia debe ser buscado entre sus argumentos empezandoa considerar ´stos de izquierda a derecha. Se busca en el primer argumento, y e si aqu´ no lo hubiera, se busca en el segundo, . . . Es evidente que al final se ı debe encontrar este par de discordancia pues hemos partido de dos t´rminos e distintos. 1

2

1 - Algoritmo de unificaci´n de Robinson o

Como se ve, hemos dado una definici´n recursiva de lo que es un par de o discordancia. Veamosalgunos ejemplos. Ejemplo 1.0 Sean los t´rminos e p(a, f (b, c), g(X)) p(a, f (X , Y ), g(h(Z )) seg´n lo dicho, el primer par de discordancia es b y X encontrados dentro del u segundo argumento como primer argumento. Obs´rvese que no hemos tomado e f (b, c) y f (X, Y ) como primer par de discordancia pues aplicando la definici´n o dada, hemos de introducirnos en este argumento ya que coinciden susfuntores y n´mero de argumentos. u Ejemplo Un par de discordancia suele expresarse entre llaves. As´ el par de discorı dancia del ejemplo anterior es {b, X}. Ejemplo 1.1 Sean los t´rminos e p(g(a, b, c), X ) p(f (X , a), Z ) En este caso, el primer par de discordancia es {g(a, b, c), f (X, a)}.
Ejemplo

Como conclusi´n podemos decir que siempre es posible encontrar un par de o discordanciaentre dos t´rminos distintos y que, en el peor de los casos, estar´ e a formado por esos dos t´rminos. e S´lo cuando dos t´rminos son iguales, no podemos encontrar el primer par o e de discordancia. Cualquier algoritmo que realice la b´squeda del primer par de u discordancia debe primero asegurarse de que no est´ ante dos t´rminos iguales. a e

´ 1.1.1 La comprobacion de apariciones
Con lacomprobaci´n de apariciones (occur check) simplemente queremos deo tectar cu´ndo una variable aparece dentro de un t´rmino. Si bien desde un a e punto de vista formal esto no ofrece ninguna complicaci´n, s´ la ofrece cuando o ı se intenta sistematizar este procedimiento. La raz´n simplemente est´ en que es tedioso tener que buscar por cada o a argumento y dentro del mismo la aparici´n de una variable. oEn cualquier caso, s´lo se trata de eso. Veamos un ejemplo. o Ejemplo 1.2 La variable X se encuentra dentro de los t´rminos p(a, f (b, X)) e y q(X, g(X, Y )) pero no de los t´rminos p(a, Z, g(a, b) y q(a, b). e Ejemplo

1.2 El algoritmo
Sean E y F dos t´rminos que queremos unificar. Consideramos inicialmente e σ0 = {} una sustituci´n vac´ es decir, que no cambia ninguna variable. Dado o ıa,...