Jump to content

Антиобъединение

Антиунификация — это процесс построения обобщения, общего для двух данных символических выражений. Как и в унификации , различают несколько фреймворков в зависимости от того, какие выражения (также называемые терминами) разрешены и какие выражения считаются равными. Если в выражении разрешены переменные, представляющие функции, процесс называется «антиунификацией высшего порядка», в противном случае — «антиунификацией первого порядка». Если требуется, чтобы обобщение имело экземпляр, буквально равный каждому входному выражению, этот процесс называется «синтаксической антиунификацией», в противном случае «Е-анти-унификация» или «теория анти-унификации по модулю».

Алгоритм антиунификации должен вычислять для заданных выражений полный и минимальный набор обобщений, то есть набор, охватывающий все обобщения и не содержащий избыточных элементов соответственно. В зависимости от структуры полный и минимальный набор обобщения может иметь один, конечное или, возможно, бесконечное количество членов или может не существовать вообще; [примечание 1] оно не может быть пустым, поскольку тривиальное обобщение в любом случае существует. За синтаксическое антиунификацию первого порядка Гордон Плоткин [1] [2] дал алгоритм, который вычисляет полный и минимальный одноэлементный набор обобщений, содержащий так называемое «наименьшее общее обобщение» (lgg).

Не следует путать антиобъединение с разъединением . Последнее означает процесс решения систем неравенств , то есть нахождения таких значений переменных, при которых все заданные неравенства удовлетворяются. [примечание 2] Эта задача существенно отличается от поиска обобщений.

Предварительные условия

[ редактировать ]

Формально антиунификационный подход предполагает

  • Бесконечный V переменных набор . Для антиобъединения более высокого порядка удобно выбрать V , непересекающуюся из множества связанных переменных лямбда-члена .
  • Множество T , таких термов что V T . Для антиунификации первого и более высокого порядка T обычно представляет собой набор термов первого порядка (терминов, построенных из символов переменных и функций) и лямбда-терминов (терминов, содержащих некоторые переменные более высокого порядка) соответственно.
  • Отношение эквивалентности на , указывая, какие члены считаются равными. Для антиобъединения более высокого порядка, как правило, если и являются альфа-эквивалентными . Для E-анти-объединения первого порядка, отражает базовые знания об определенных функциональных символах; например, если считается коммутативным, если результат путем замены аргументов в некоторых (возможно, во всех) случаях. [примечание 3] Если фоновых знаний вообще нет, то равными считаются только буквально или синтаксически идентичные термины.

Срок первого порядка

[ редактировать ]

Учитывая набор переменных символов, набор постоянных символов и множеств из -арные функциональные символы, также называемые операторными символами, для каждого натурального числа , набор термов (несортированного первого порядка) как рекурсивно определяется наименьшее множество со следующими свойствами: [3]

  • каждый переменный символ является термом: V T ,
  • каждый постоянный символ является термом: C T ,
  • из каждых n термов t 1 ,..., t n и каждого n -арного функционального символа f F n больший терм можно построить.

Например, если x V — переменный символ, 1 € C — константа, а add € F 2 — символ двоичной функции, то x T , 1 € T и (следовательно) add( x ,1) ∈ T по первому, второму и третьему правилам построения членов соответственно. Последний термин обычно записывается как x +1, используя для удобства инфиксную нотацию и более распространенный символ оператора +.

Член высшего порядка

[ редактировать ]

Замена это отображение от переменных к термам; обозначение относится к замене, отображающей каждую переменную к сроку , для и каждая другая переменная сама по себе. Применение этой замены к термину t записывается в постфиксной записи как ; это означает (одновременную) замену каждого вхождения каждой переменной срок t в . Результат применения замены σ к термину t называется экземпляром этого термина t .В качестве примера первого порядка, применив замену к сроку

е ( х , а , г ( С ), и ) урожайность
е ( есть ,y) , а , г ( б ), и ) .

Обобщение, специализация

[ редактировать ]

Если срок имеет экземпляр, эквивалентный термину , то есть, если для какой-то замены , затем называется более общим, чем , и называется более специальным , чем или отнесенным к нему, . Например, является более общим, чем если коммутативен , поскольку тогда .

Если является буквальной (синтаксической) идентичностью терминов, термин может быть как более общим, так и более специальным, чем другой, только в том случае, если оба термина различаются только именами переменных, а не синтаксической структурой; такие термины называются вариантами или переименованиями друг друга.Например, это вариант , с и .Однако, это не вариант , поскольку никакая замена не может превратить последний член в первый, хотя достигает обратного направления.Следовательно, последний термин более специальный, чем первый.

Замена более специфичен , чем замена или отнесен к ней если является более особенным, чем для каждой переменной .Например, является более особенным, чем , с и является более особенным, чем и , соответственно.

Проблема антиунификации, множество обобщений

[ редактировать ]

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

Синтаксическое антиунификация первого порядка

[ редактировать ]

Структура синтаксической антиунификации первого порядка основана на являющийся набором термов первого порядка (по некоторому заданному множеству переменных, констант и из -арные функциональные символы) и на равенство синтаксическое .В этих рамках каждая проблема, направленная против объединения, имеет полный и, очевидно, минимальный набор одноэлементных решений . Его член называется наименьшим общим обобщением (lgg) задачи, оно имеет экземпляр, синтаксически равный и еще один, синтаксически равный .Любое общее обобщение и включает в себя .lgg уникален с точностью до вариантов: если и являются как полным, так и минимальным набором решений одной и той же синтаксической проблемы антиунификации, тогда и на некоторые условия и , которые являются переименованиями друг друга.

Плоткин [1] [2] дал алгоритм для вычисления lgg двух заданных терминов.Оно предполагает инъективное отображение , то есть отображение, присваивающее каждой паре терминов собственная переменная , так что никакие две пары не имеют одну и ту же переменную. [примечание 4] Алгоритм состоит из двух правил:

если предыдущее правило неприменимо

Например, ; это наименее общее обобщение отражает общее свойство обоих входных данных — квадратные числа.

Плоткин использовал свой алгоритм для вычисления « относительного наименьшего общего обобщения (rlgg) » двух наборов предложений в логике первого порядка, что было основой подхода Голема к индуктивному логическому программированию .

Теория антиобъединения первого порядка по модулю

[ редактировать ]
  • Якобсен, Эрик (июнь 1991 г.), Унификация и антиунификация (PDF) , Технический отчет
  • Оствальд, Бьярте М. (апрель 2004 г.), Функциональная реконструкция антиунификации (PDF) , NR Note, vol. DART/04/04, Норвежский вычислительный центр
  • Бойчева, Светла; Марков, Здравко (2002). «Алгоритм наименьшего обобщения при относительной импликации» . Учеб. ФЛЕРС-02 . АААИ. стр. 322–326.
  • Куция, Темур; Леви, Хорди; Вилларе, Матеу (2014). «Противоунификация условий и хеджирования без рейтинга» (PDF) . Журнал автоматизированного рассуждения . 52 (2): 155–190. дои : 10.1007/s10817-013-9285-6 . Программное обеспечение.

Эквациональные теории

[ редактировать ]

Сортированное антиобъединение первого порядка

[ редактировать ]

Номинальное антиобъединение

[ редактировать ]

Приложения

[ редактировать ]

Антиобъединение высшего порядка

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Полные наборы обобщения всегда существуют, но может случиться так, что каждый полный набор обобщения не является минимальным.
  2. ^ В 1986 году Комон назвал решение неравенств «антиобъединением», что в наши дни стало довольно необычным. Комон, Хьюберт (1986). «Достаточная полнота, системы переписывания терминов и «антиунификация» ». Учеб. 8-я Международная конференция по автоматизированному дедукции . ЛНКС. Том. 230. Спрингер. стр. 128–140.
  3. ^ Например
  4. ^ С теоретической точки зрения такое отображение существует, поскольку оба и являются счетно-бесконечными множествами; для практических целей, можно создавать по мере необходимости, запоминая назначенные сопоставления в хеш-таблице .
  1. ^ Jump up to: а б Плоткин, Гордон Д. (1970). Мельцер, Б.; Мичи, Д. (ред.). «Заметка об индуктивном обобщении». Машинный интеллект . 5 : 153–163.
  2. ^ Jump up to: а б Плоткин, Гордон Д. (1971). Мельцер, Б.; Мичи, Д. (ред.). «Дальнейшее примечание об индуктивном обобщении». Машинный интеллект . 6 : 101–124.
  3. ^ СиСи Чанг; Х. Джером Кейслер (1977). А. Хейтинг; Х. Дж. Кейслер; А. Мостовский; А. Робинсон; П. Суппес (ред.). Теория моделей . Исследования по логике и основам математики. Том. 73. Северная Голландия. ; здесь: Раздел 1.3
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 44bacc211ce00f4ce3bffa48074924c6__1712049780
URL1:https://arc.ask3.ru/arc/aa/44/c6/44bacc211ce00f4ce3bffa48074924c6.html
Заголовок, (Title) документа по адресу, URL1:
Anti-unification - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)