Cтраница 3
В настоящее время существует несколько алгоритмов унификации, которые отличаются от алгоритма унификации, предложенного Робинсоном. Фиттинг предложил реализацию алгоритма унификации на языке Пролог, которая имеет следующие особенности. Во-вторых, в предложенном алгоритме не выполняется вычисление композиции подстановок, а происходит запоминание каждой связки. [31]
Мы можем, однако, использовать процедуру АС-пополнения, которая включает аксиомы коммутативности и ассоциативности в алгоритм унификации. [32]
В настоящее время существует несколько алгоритмов унификации, которые отличаются от алгоритма унификации, предложенного Робинсоном. Фиттинг предложил реализацию алгоритма унификации на языке Пролог, которая имеет следующие особенности. Во-вторых, в предложенном алгоритме не выполняется вычисление композиции подстановок, а происходит запоминание каждой связки. [33]
Важным вопросом, касающимся интерпретатора языка Пролог, является предположение о замкнутом мире. В исчислении предикатов доказательство - Р ( х) предполагает, что Р ( х) ложно при каждой интерпретации. Интерпретатор языка Пролог на основе алгоритма унификации предлагает более ограниченный вариант, чем нахождение опровержения методом резолюции. Вместо рассмотрения всех интерпретаций, он исследует только те, которые явно присутствуют в базе данных. [34]
Ветвь считается замкнутой, если она содержит литеры X и - Y, где X и Y унифицируемы. В реализации метода аналитичческих таблиц используется реализация алгоритма унификации, составленная Стирлингом и Шапиро. [35]
Необходимо предусмотреть работу дедуктивного вывода в открытой проблемной области. Рассмотрим процесс дедуктивного вывода более подробно. В процесс дедуктивного вывода вовлекаются два важных алгоритма: алгоритм сколемизации и алгоритм унификации. Эти алгоритмы в MLL являются дальнейшим развитием соответствующих алгоритмов исчисления предикатов первого порядка. Исходная формула для алгоритма сколемизации должна быть представлена в пренексной нормальной форме. [36]
На практике обычно унификаторы можно легко определять, сравнивая по очереди соответствующие аргументы предикатов и выписывая те присваивания термов переменным, которые сделали бы эти аргументы одинаковыми. Для поиска унификаторов в сложных случаях и для реализации на ЭВМ имеются систематические алгоритмы унификации ( см. гл. На этом этапе будет, вероятно, полезно рассмотреть несколько простых примеров унификации и резолюции, которые приводятся ниже. [37]
Другое возможное решение состоит в следующем: поскольку переписывающий метод весьма эффективен при обращении с термами, почему бы не применять резолюцию к дизъюнктам, а переписывающий метод ( с канонической системой для Т) - к аргументам. Несмотря на кажущуюся правдоподобность, этот подход не полон. Исследования в этом направлении проводились Плоткиным [37], который погружал аксиомы области в алгоритм унификации ( та же идея была позже приспособлена в [27, 34] для расширения метода Кнута - Бендикса), Слэглом [44], Лэнкфордом [26], а также Лэнкфордом и Баллантайном [29], которые ввели понятие сужения для поиска полезных примеров аргументов в дизъюнктах. [38]
Эти два выражения не тождественны. Чтобы отождествить Р ( а) и Р ( х), мы сперва должны найти рассогласование, а затем попытаться его исключить. Так как л - переменная, то х можно заменить на а, и таким образом рассогласова ние будет исключено. В этом и заключается идея, на которой основан алгоритм унификации. [39]
Тот, кто знаком с АС-унификацией и АС-пополнением [34], должно быть, заметил, что в рассмотренном примере мы породили далеко не все критические пары. Отбрасывание таких критических пар было умышленным, поскольку полнота нашей стратегии от них не зависит. Более того, порождение всех критических пар процедурой АС-пополнения требует полного алгоритма АС-унификации и для -) -, и для, который довольно неэффективен. Те критические пары, которые нам нужно порождать, образуют лишь небольшое подмножество всех возможных критических пар, и требуемый для их порождения алгоритм унификации значительно проще, чем АС-унификация. Для того чтобы описать, какие же критические пары следует порождать, мы начнем с определения. [40]