¿Cuál es el óptimo "más general unificador" algoritmo?

Question

La Pregunta

¿Cuál es el más eficiente de la MGU algoritmo?¿Cuál es su tiempo de complejidad?Es lo suficientemente simple como para describir como un desbordamiento de la pila de respuesta?

He estado tratando de encontrar la respuesta en Google, pero seguir buscando privado .Los archivos pdf que sólo puedo acceder a través de un ACM de suscripción.

He encontrado una discusión en el SICP: aquí

Explicación de qué es un "más general algoritmo de unificación" es:Tomar dos árboles de expresión que contiene "variables libres" y "constantes"...por ejemplo,

 e1 = (+ x? (* y? 3) 5)
 e2 = (+ z? q? r?)

A continuación, el Unificador Más General el algoritmo devuelve el mayor general conjunto de enlaces que hace que las dos expresiones equivalentes.

es decir,

mgu(e1,e2) = (x = z), q = (* y 3), y = unbound, r = 5

Por "más general", en su lugar podría enlazar (x = 1) y (z = 1) y que también haría e1 y e2 equivalente pero sería más específico.

El SICP artículo parece dar a entender que es razonablemente caro.

Para info, la razón por la que estoy preguntando es porque sé que tipo de inferencia también implica esta "unificación" algoritmo y me gustaría entenderlo.

Answer 1

El algorith simple que se utiliza en la práctica (por ejemplo, en Prolog) es exponencial para los casos patológicos.

No es un algoritmo teóricamente más eficiente por Martelli y Montanari (IIRC es lineal), pero es mucho más lento para los casos simples que se producen en la práctica, por lo que no se utiliza mucho.

Answer 2

Baader y Snyder publicó varios algoritmos de unificación, tanto para sintáctica la unificación y la unificación ecuacional.

Afirman que su tercer algoritmo de unificación sintáctica (en la sección 2.3) se ejecuta en O (n alpha (n)) donde alpha (n) es la función de Ackermann inversa -. En situaciones prácticas que es equivalente a una pequeña constante