Cтраница 2
После того, как Робинсон [ Robi65 ] опубликовал свой алгоритм унификации, Лавленд в 1970 г. впервые предложил линейную резолюцию с правилом выбора. [16]
Следует отметить, что существуют и другие подходы к созданию алгоритмов унификации. Один из таких подходов основан на нахождении согласующейся ( concurrent) унификации. Вместо подстановки сг, унифицирующей термы t и и, удобно иногда говорить, что имеется решение уравнения t и. Предположим, что мы имеем уравнения to Wo ti Wi... Подстановка а является результатом решения каждого уравнения. [17]
Поскольку существует необходимость в унификации более чем одной пары термов, разработан алгоритм многократной унификации, в основе которого лежит процедура сведения к бинарной унификации. Рассмотрим алгоритм многократной унификации. [18]
Далее приведем определение расширенного представления дерева, которое является более удобным для реализации алгоритма унификации. [19]
На более мелких шагах параллелизма можно достигнуть путем реализации его, насколько это возможно, в алгоритме унификации. Это может привести к значительному повышению эффективности даже последовательного Пролога. [20]
Здесь мы должны заметить, что во многих приложениях в целях большей эффективности процедура поиска вывода ПРОЛОГа, основанная на алгоритме унификации, не осуществляет проверку вхождений. Другими словами, она подставляет первый терм из текущего DS вместо первой переменной из этого множества. Это, конечно, может привести к неверным результатам, поэтому программисту приходится создавать в программе соответствующие средства защиты для избежания таких ошибок. [21]
При этом в качестве дедуктивной машины будет выступать сам внутренний механизм работы системы PDC Prolog, который основывается на методе резолюций и алгоритме унификации. [22]
Отметим, что основными способами устранения причин экспоненциального взрыва, имеющего место при доказательстве теорем практической сложности, являются использование семантики, различных эвристик и встраивание в правила вывода и алгоритмы унификации специфики конкретной предметной области. [23]
Поскольку существует необходимость в унификации более чем одной пары термов, разработан алгоритм многократной унификации, в основе которого лежит процедура сведения к бинарной унификации. Рассмотрим алгоритм многократной унификации. [24]
Следовательно, алгоритм унификации завершается, и мы заключаем, что W не унифицируемо. [25]
В настоящее время известно огромное множество различных версий алгоритмов унификации. Ниже мы рассмотрим алгоритм унификации, введенный Робинсоном, для принципа резолюции, поскольку именно этот алгоритм выбран Фиттингом для реализации метода автоматического доказательства теорем на основе аналитических таблиц. [26]
Далее мы приведем теоретические положения, на которых базируется метод автоматического доказательства теорем на основе аналитических таблиц для логики предикатов 1-го порядка. Отметим, что вышеописанный алгоритм унификации играет в этом методе ключевую роль. [27]
Далее изучаются аксиоматический метод доказательства, метод таблиц Бета и метод резолюций. Метод резолюций вместе с алгоритмом унификации положен в основу логического программирования. Для обоснования этих методов приводятся соответствующие теоремы корректности и полноты. [28]
В настоящее время существует несколько алгоритмов унификации, которые отличаются от алгоритма унификации, предложенного Робинсоном. Фиттинг предложил реализацию алгоритма унификации на языке Пролог, которая имеет следующие особенности. Во-вторых, в предложенном алгоритме не выполняется вычисление композиции подстановок, а происходит запоминание каждой связки. [29]
Причина упрощения состоит в том, что процесс унификации, требуемый для нахождения этих критических пар, может быть ограничен только работой с N-термами, и оператор - - ( который в N-термах не встречается) совсем не нужно рассматривать. В соответствии с этим мы приведем сейчас алгоритм унификации, требуемый для нахождения указанных критических пар. [30]