Metodo De Resolucion De Robinson

Cap´ıtulo 1
Algoritmo de unificaci´n de Robinsono
´1.0 Introduccion
Con objeto de encontrar el unificador de m´xima generalidad de dos t´rminosae
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.on
La claridad del m´todo utilizado por el algoritmo lo hace muy util, tantoe´
desde unpunto de vista did´ctico como desde un punto de vista de implemen-a
taci´n.o
Vamos a exponer el m´todo en un cuadro general y posteriormente lo apli-e
caremos a varios ejemplos.
Para la mejor comprensi´n del algoritmo damos unas nociones previas queo
ser´n de utilidad.a
´1.1 Elementos para el algoritmo de unificacion
Entre los elementosque vamos a considerar se encuentran el llamado primer
par de discordancia entre dos t´rminos, y la aparici´n de variables dentro de uneo
t´rmino occur check (comprobaci´n de apariciones).eo
1.1.0 Primer par de discordancia
Tomemos dos t´rminos que no sean iguales. Eso significa que habr´ algunaea
diferencia entre ellos. Esta diferencia puede hallarse en el nombre del funtor, en
el n´mero deargumentos, o en alguno de los argumentos.u
Si la diferencia est´ en el nombre del funtor, el primer par de discordanciaa
es la pareja formada por los dos t´rminos. Si est´ en el n´mero de argumentos,eau
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, eluprimer par de discordancia debe ser buscado entre sus argumentos empezando
a considerar ´stos de izquierda a derecha. Se busca en el primer argumento, ye
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´rminose
distintos.
1

2
1 - Algoritmo de unificaci´n de Robinsono
Como se ve, hemosdado una definici´n recursiva de lo que es un par deo
discordancia. Veamos algunos ejemplos.
Ejemplo 1.0 Sean los t´rminose
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 delu
segundo argumento como primer argumento. Obs´rvese que no hemos tomadoe
f (b, c) y f (X, Y ) como primer par de discordancia pues aplicando ladefinici´no
dada, hemos de introducirnos en este argumento ya que coinciden sus funtores
y n´mero de argumentos.uEjemplo
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´rminose
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
Comoconclusi´n podemos decir que siempre es posible encontrar un par deo
discordancia entre dos t´rminos distintos y que, en el peor de los casos, estar´ea
formado por esos dos t´rminos.e
S´lo cuando dos t´rminos son iguales, no podemos encontrar el primer paroe
de discordancia. Cualquier algoritmo que realice la b´squeda del primer par deu
discordancia debe primero asegurarse de que no est´ante dos t´rminos iguales.ae
´1.1.1 La comprobacion de apariciones
Con la comprobaci´n de apariciones (occur check) simplemente queremos de-o
tectar cu´ndo una variable aparece dentro de un t´rmino. Si bien desde unae
punto de vista formal esto no ofrece ninguna complicaci´n, s´ la ofrece cuandooı
se intenta sistematizar este procedimiento.
La raz´n simplemente est´ enque es tedioso tener que buscar por cadaoa
argumento y dentro del mismo la aparici´n de una variable.o
En 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).eEjemplo
1.2 El algoritmo
Sean E y F dos t´rminos que queremos unificar....