Каков оптимальный алгоритм «наиболее общего объединения»?

Question

Вопрос

Какой алгоритм MGU наиболее эффективен? Какова его временная сложность? Это достаточно просто описать как ответ переполнения стека?

Я пытался найти ответ в Google, но продолжаю находить частные .PDF, к которым я могу получить доступ только через подписку ACM.

Я нашел одно обсуждение в SICP: здесь

Объяснение того, что такое "самый общий алгоритм объединения": Возьмите два дерева выражений, содержащих «свободные переменные» и «константы» ... например,

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

Тогда алгоритм Most General Unifier возвращает наиболее общий набор привязок, который делает два выражения эквивалентными.

т.е.

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

С помощью «наиболее общего» вы можете вместо этого связать (x = 1) и (z = 1), что также сделает e1 и e2 эквивалентными, но это будет более конкретным.

Статья SICP, по-видимому, подразумевает, что она достаточно дорогая.

Для информации, я спрашиваю, потому что я знаю, что вывод типа также включает в себя этот алгоритм "объединения", и я хотел бы понять его.

Answer 1

Простой алгоритм, который используется на практике (например, в Прологе), экспоненциальный для патологических случаев.

Существует теоретически более эффективный алгоритм Мартелли и Монтанари (IIRC он линейный), но он намного медленнее для простых случаев, которые встречаются на практике, поэтому он не используется много.

Answer 2

Баадер и Снайдер опубликовали несколько алгоритмов унификации, как для синтаксической, так и для эквалайзерной унификации.

Они заявляют, что их третий алгоритм синтаксического объединения (в разделе 2.3) работает в O (n alpha (n)), где alpha (n) - обратная функция Аккермана - в практических ситуациях это эквивалентно небольшой константе.