Алгоритм завершения Кнута – Бендикса - Knuth–Bendix completion algorithm

В Алгоритм завершения Кнута – Бендикса (названный в честь Дональд Кнут и Питер Бендикс^[1]) это полурешение^[2][3] алгоритм для преобразования набора уравнения (над термины ) в сливаться система переписывания терминов. Когда алгоритм успешен, он эффективно решает проблема со словом для указанного алгебра.

Алгоритм Бухбергера для вычислений Базы Грёбнера очень похожий алгоритм. Хотя он был разработан независимо, он также может рассматриваться как реализация алгоритма Кнута – Бендикса в теории кольца многочленов.

Вступление

Для набора E уравнений, его дедуктивное замыкание (⁎⟷E) - это совокупность всех уравнений, которые можно получить, применяя уравнения из E в любом порядке. E считается бинарное отношение, (⟶E) это его переписать закрытие, и (⁎⟷E) это закрытие эквивалентности из (⟶E) .Для набора р правил перезаписи, его дедуктивное замыкание (⁎⟶р ∘ ⁎⟵р) представляет собой набор всех уравнений, который может быть подтвержден применением правил из р слева направо в обе стороны, пока они не станут буквально равными. р снова рассматривается как бинарное отношение, (⟶р) - его закрытие перезаписи, (⟵р) это его разговаривать, и (⁎⟶р ∘ ⁎⟵р) это состав отношений от их рефлексивные переходные замыкания (⁎⟶р и ⁎⟵р).

Например, если E = {1⋅Икс = Икс, Икс⁻¹⋅Икс = 1, (Икс⋅у)⋅z = Икс⋅(у⋅z)} являются группа аксиомы, производная цепочка

а⁻¹⋅(а⋅б)   ⁎⟷E   (а⁻¹⋅а)⋅б   ⁎⟷E   1⋅б   ⁎⟷E   б

демонстрирует, что а⁻¹⋅(а⋅б) ⁎⟷E б является членом E 's дедуктивное замыкание. р = { 1⋅Икс → Икс, Икс⁻¹⋅Икс → 1, (Икс⋅у)⋅z → Икс⋅(у⋅z) } это версия "правила перезаписи" E, цепочки вывода

(а⁻¹⋅а)⋅б   ⁎⟶р   1⋅б   ⁎⟶р   б и б   ⁎⟵р   б

продемонстрировать, что (а⁻¹⋅а)⋅б ⁎⟶р∘⁎⟵р б является членом Р's дедуктивное замыкание. Однако нет способа вывести а⁻¹⋅(а⋅б) ⁎⟶р∘⁎⟵р б аналогично приведенному выше, поскольку применение правила справа налево (Икс⋅у)⋅z → Икс⋅(у⋅z) не допускается.

Алгоритм Кнута – Бендикса принимает набор E уравнений между термины, а заказ на сокращение (>) по набору всех терминов и пытается построить сливающуюся и завершающую систему переписывания терминов р который имеет то же дедуктивное закрытие, что и E.При доказательстве последствий от E часто требует человеческой интуиции, доказывая последствия от р не делает. Подробнее см. Confluence (абстрактное переписывание) # Мотивирующие примеры, который дает пример доказательства из теории групп, выполненный как с использованием E и используя р.

Правила

Учитывая набор E уравнений между термины, следующие правила вывода могут быть использованы для преобразования его в эквивалент конвергентная система перезаписи терминов (если возможно):^[4][5]Они основаны на заданном пользователем заказ на сокращение (>) по совокупности всех терминов; он повышается до хорошо обоснованного порядка (▻) на множестве правил перезаписи путем определения (s → т) ▻ (л → р) если

• s >е л, или же
• s и л находятся буквально похоже и т > р.

Удалить	‹ E∪{s = s}	, р ›	⊢	‹ E	, р ›
Сочинять	‹ E	, р∪{s → т} ›	⊢	‹ E	, р∪{s → ты} ›	если т ⟶р ты
Упрощать	‹ E∪{s = т}	, р ›	⊢	‹ E∪{s = ты}	, р ›	если т ⟶р ты
Ориент	‹ E∪{s = т}	, р ›	⊢	‹ E	, р∪{s → т} ›	если s > т
Крах	‹ E	, р∪{s → т} ›	⊢	‹ E∪{ты = т}	, р ›	если s ⟶р ты к л → р с (s → т) ▻ (л → р)
Вывести	‹ E	, р ›	⊢	‹ E∪{s = т}	, р ›	если (s,т) это критическая пара из р

Пример

Следующий пример запуска, полученный из Доказательство теорем, вычисляет завершение (аддитивных) групповых аксиом, как в Knuth, Bendix (1970). Он начинается с трех исходных уравнений для группы (нейтральный элемент 0, обратные элементы, ассоциативность), используя f (X, Y) за Икс+Y, и я (Х) для -Икс. 10 уравнений, отмеченных «final», представляют собой получившуюся сходящуюся систему перезаписи. «Pm» - это сокращение от «pm».парамодуляция ", реализуя выводить. Вычисление критических пар - это пример парамодуляции для предложений эквациональных единиц. "Rw" переписывает, реализует сочинять, крах, и упрощать. Ориентирование уравнений выполняется неявно и не записывается.

      1:: [++ equal (f (X1,0), X1)]: initial ("GROUP.lop", at_line_9_column_1) 2:: [++ equal (f (X1, i (X1)), 0)] : initial ("GROUP.lop", at_line_12_column_1) 3:: [++ equal (f (f (X1, X2), X3), f (X1, f (X2, X3)))]: initial ("GROUP. lop ", at_line_15_column_1) 5:: [++ equal (f (X1, X2), f (X1, f (0, X2)))]: pm (3,1) 6:: [++ equal (f ( X1, f (X2, i (f (X1, X2)))), 0)]: pm (2,3) 7:: [++ equal (f (0, X2), f (X1, f (i (X1), X2)))]: pm (3,2) 27:: [++ equal (f (X1,0), f (0, i (i (X1))))]: pm (7, 2) 36:: [++ equal (X1, f (0, i (i (X1))))]: rw (27,1) 46:: [++ equal (f (X1, X2), f ( X1, i (i (X2))))]: pm (5,36) 52:: [++ equal (f (0, X1), X1)]: rw (36,46) 60:: [++ equal (i (0), 0)]: pm (2,52) 63:: [++ equal (i (i (X1)), f (0, X1))]: pm (46,52) 64: : [++ equal (f (X1, f (i (X1), X2)), X2)]: rw (7,52) 67:: [++ equal (i (i (X1)), X1)] : rw (63,52) 74:: [++ equal (f (i (X1), X1), 0)]: pm (2,67) 79:: [++ equal (f (0, X2), f (i (X1), f (X1, X2)))]: pm (3,74) 83:: [++ equal (X2, f (i (X1), f (X1, X2)))]:rw (79,52) 134:: [++ equal (f (i (X1), 0), f (X2, i (f (X1, X2))))]: pm (83,6) 151:: [++ equal (i (X1), f (X2, i (f (X1, X2))))]: rw (134,1) 165:: [++ equal (f (i (X1), i ( X2)), i (f (X2, X1)))]: pm (83,151) 239:: [++ equal (f (X1,0), X1)]: 1: 'final' 240:: [++ equal (f (X1, i (X1)), 0)]: 2: 'final' 241:: [++ equal (f (f (X1, X2), X3), f (X1, f (X2, X3) )))]: 3: 'final' 242:: [++ equal (f (0, X1), X1)]: 52: 'final' 243:: [++ equal (i (0), 0)] : 60: 'final' 244:: [++ equal (i (i (X1)), X1)]: 67: 'final' 245:: [++ equal (f (i (X1), X1), 0 )]: 74: 'final' 246:: [++ equal (f (X1, f (i (X1), X2)), X2)]: 64: 'final' 247:: [++ equal (f ( i (X1), f (X1, X2)), X2)]: 83: 'final' 248:: [++ equal (i (f (X1, X2)), f (i (X2), i (X1 )))]: 165: 'финал'

Смотрите также Проблема со словами (математика) для другого представления этого примера.

Системы переписывания струн в теории групп

Важный случай в вычислительная теория групп системы перезаписи строк, которые можно использовать для присвоения канонических меток элементам или смежные классы из конечно представленная группа как продукты генераторы. Этому особому случаю и посвящен данный раздел.

Мотивация в теории групп

В лемма о критической паре заявляет, что система переписывания терминов локально сливной (или слабо сливной) тогда и только тогда, когда все ее критические пары сходятся. Кроме того, у нас есть Лемма Ньюмана который утверждает, что если (абстрактная) система перезаписи сильно нормализующий и слабо сливной, то система перезаписи сливная. Итак, если мы можем добавить правила к системе перезаписи терминов, чтобы заставить все критические пары сходиться, сохраняя при этом свойство сильной нормализации, то это заставит результирующую систему перезаписи стать конфлюэнтной.

Рассмотрим конечно представленный моноид ${\displaystyle M=\langle X\mid R\rangle }$ где X - конечное множество образующих, а R - множество определяющих соотношений на X. Пусть X^* - множество всех слов в X (т.е. свободный моноид, порожденный X). Поскольку отношения R порождают отношение эквивалентности на X *, можно рассматривать элементы M как классы эквивалентности X^* под Р. Для каждого класса {w₁, w₂, ... } желательно выбрать стандартного представителя ш_k. Этот представитель называется канонический или же нормальная форма за каждое слово ш_k в классе. Если существует вычислимый метод определения для каждого ш_k его нормальная форма ш_я тогда проблема со словом легко решается. Конфлюентная система перезаписи позволяет делать именно это.

Хотя выбор канонической формы теоретически может быть сделан произвольным образом, этот подход, как правило, не вычислим. (Учтите, что отношение эквивалентности в языке может порождать бесконечное число бесконечных классов.) Если язык является хорошо организованный тогда порядок <дает последовательный метод определения минимальных представителей, однако вычисление этих представителей все еще может быть невозможно. В частности, если для вычисления минимальных представителей используется система перезаписи, то порядок <также должен иметь свойство:

A

Это свойство называется инвариантность перевода. Порядок, который является как трансляционно-инвариантным, так и исправным, называется порядком. порядок уменьшения.

Из представления моноида можно определить систему перезаписи, задаваемую отношениями R. Если A x B находится в R, то либо A B и A → B. Поскольку <- порядок редукции, данное слово W может быть сокращено W> W_1> ...> W_n, где W_n неприводимо по системе переписывания. Однако в зависимости от правил, применяемых на каждом W_я → W_{я + 1} можно получить две разные неприводимые редукции W_п ≠ W '_м of W. Однако, если система перезаписи, заданная отношениями, преобразована в конфлюэнтную систему перезаписи с помощью алгоритма Кнута – Бендикса, то все сокращения гарантированно дают одно и то же несократимое слово, а именно нормальную форму для этого слова.

Описание алгоритма конечно представленных моноидов

Предположим, нам дан презентация ${\displaystyle \langle X\mid R\rangle }$, куда ${\displaystyle X}$ это набор генераторы и ${\displaystyle R}$ это набор связи давая систему перезаписи. Предположим далее, что у нас есть порядок редукции ${\displaystyle <}$ среди слов, порожденных ${\displaystyle X}$(например., заказ шортлекс ). Для каждого отношения ${\displaystyle P_{i}=Q_{i}}$ в ${\displaystyle R}$, предполагать ${\displaystyle Q_{i}<P_{i}}$. Итак, мы начинаем с набора редукций ${\displaystyle P_{i}\rightarrow Q_{i}}$.

Во-первых, если какое-либо отношение ${\displaystyle P_{i}=Q_{i}}$ можно уменьшить, заменить ${\displaystyle P_{i}}$ и ${\displaystyle Q_{i}}$ со скидками.

Затем мы добавляем дополнительные сокращения (то есть правила переписывания), чтобы исключить возможные исключения из слияния. Предположим, что ${\displaystyle P_{i}}$ и ${\displaystyle P_{j}}$, куда ${\displaystyle i\neq j}$, перекрывать.

1. Случай 1: либо префикс ${\displaystyle P_{i}}$ равен суффиксу ${\displaystyle P_{j}}$, или наоборот. В первом случае мы можем написать ${\displaystyle P_{i}=BC}$ и ${\displaystyle P_{j}=AB}$; в последнем случае, ${\displaystyle P_{i}=AB}$ и ${\displaystyle P_{j}=BC}$.
2. Случай 2: либо ${\displaystyle P_{i}}$ полностью содержится в (окружен) ${\displaystyle P_{j}}$, или наоборот. В первом случае мы можем написать ${\displaystyle P_{i}=B}$ и ${\displaystyle P_{j}=ABC}$; в последнем случае, ${\displaystyle P_{i}=ABC}$ и ${\displaystyle P_{j}=B}$.

Сократить слово ${\displaystyle ABC}$ с помощью ${\displaystyle P_{i}}$ сначала, затем используя ${\displaystyle P_{j}}$ первый. Назовите результаты ${\displaystyle r_{1},r_{2}}$, соответственно. Если ${\displaystyle r_{1}\neq r_{2}}$, то у нас есть случай, когда слияние может не сработать. Следовательно, добавляем редукцию ${\displaystyle \max r_{1},r_{2}\rightarrow \min r_{1},r_{2}}$ к ${\displaystyle R}$.

После добавления правила в ${\displaystyle R}$, удалите все правила в ${\displaystyle R}$ которые могли бы иметь приводимые левые части.

Повторяйте процедуру до тех пор, пока не будут проверены все перекрывающиеся левые стороны.

Примеры

Завершающий пример

Рассмотрим моноид:

${\displaystyle \langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle }$.

Мы используем заказ шортлекс. Это бесконечный моноид, но, тем не менее, алгоритм Кнута – Бендикса может решить проблему слов.

Таким образом, наши первые три сокращения

${\displaystyle x^{3}\rightarrow 1}$

(1)

${\displaystyle y^{3}\rightarrow 1}$

(2)

${\displaystyle (xy)^{3}\rightarrow 1}$.

(3)

Суффикс ${\displaystyle x^{3}}$ (а именно ${\displaystyle x}$) является префиксом ${\displaystyle (xy)^{3}=xyxyxy}$, так что рассмотрите слово ${\displaystyle x^{3}yxyxy}$. Сокращение использования (1), мы получили ${\displaystyle yxyxy}$. Сокращение использования (3), мы получили ${\displaystyle x^{2}}$. Отсюда получаем ${\displaystyle yxyxy=x^{2}}$, давая правило редукции

${\displaystyle yxyxy\rightarrow x^{2}}$.

(4)

Аналогично, используя ${\displaystyle xyxyxy^{3}}$ и сокращение использования (2) и (3), мы получили ${\displaystyle xyxyx=y^{2}}$. Следовательно, сокращение

${\displaystyle xyxyx\rightarrow y^{2}}$.

(5)

Оба эти правила устарели (3), поэтому снимаем его.

Далее рассмотрим ${\displaystyle x^{3}yxyx}$ путем перекрытия (1) и (5). Уменьшая мы получаем ${\displaystyle yxyx=x^{2}y^{2}}$, поэтому мы добавляем правило

${\displaystyle yxyx\rightarrow x^{2}y^{2}}$.

(6)

Учитывая ${\displaystyle xyxyx^{3}}$ путем перекрытия (1) и (5), мы получили ${\displaystyle xyxy=y^{2}x^{2}}$, поэтому мы добавляем правило

${\displaystyle y^{2}x^{2}\rightarrow xyxy}$.

(7)

Эти устаревшие правила (4) и (5), поэтому убираем их.

Теперь у нас осталась система перезаписи

${\displaystyle x^{3}\rightarrow 1}$

(1)

${\displaystyle y^{3}\rightarrow 1}$

(2)

${\displaystyle yxyx\rightarrow x^{2}y^{2}}$

(6)

${\displaystyle y^{2}x^{2}\rightarrow xyxy}$.

(7)

Проверяя совпадения этих правил, мы не находим потенциальных сбоев слияния. Следовательно, у нас есть сливная система перезаписи, и алгоритм успешно завершается.

Непрерывный пример

Порядок генераторов может существенно повлиять на то, завершится ли завершение Кнута – Бендикса. В качестве примера рассмотрим свободная абелева группа по представлению моноида:

${\displaystyle \langle x,y,x^{-1},y^{-1}\,|\,xy=yx,xx^{-1}=x^{-1}x=yy^{-1}=y^{-1}y=1\rangle .}$

Пополнение Кнута – Бендикса по лексикографическому порядку ${\displaystyle x<x^{-1}<y<y^{-1}}$ заканчивается конвергентной системой, однако с учетом лексикографического порядка длины ${\displaystyle x<y<x^{-1}<y^{-1}}$ он не заканчивается, поскольку не существует конечных сходящихся систем, совместимых с этим последним порядком.^[6]

Обобщения

Если Кнут-Бендикс не преуспеет, он либо будет работать вечно, либо потерпит неудачу, когда встретит неориентируемое уравнение (т.е. уравнение, которое оно не может превратить в правило перезаписи). Расширенный завершение без сбоев не потерпит неудачу с неориентируемыми уравнениями и обеспечивает процедура полурешения для слова проблема.

Понятие записанная перезапись Обсуждаемая в статье Хейворта и Венсли, указанная ниже, позволяет выполнять некоторую запись или протоколирование процесса перезаписи по мере его выполнения. Это полезно для вычисления тождеств между отношениями для представления групп.

Рекомендации

1. Д. Кнут, "Происхождение грамматик атрибутов"
2. Джейкоб Т. Шварц; Доменико Кантоне; Эухенио Г. Омодео; Мартин Дэвис (2011). Вычислительная логика и теория множеств: применение формализованной логики к анализу. Springer Science & Business Media. п. 200. ISBN  978-0-85729-808-9.
3. Hsiang, J .; Русинович, М. (1987). «О задачах слова в эквациональных теориях» (PDF). Автоматы, языки и программирование. Конспект лекций по информатике. 267. п. 54. Дои:10.1007/3-540-18088-5_6. ISBN  978-3-540-18088-3., п. 55
4. Bachmair, L .; Dershowitz, N .; Сян Дж. (Июнь 1986 г.). «Заказы на уравнительные доказательства». Proc. Симпозиум IEEE по логике в компьютерных науках. С. 346–357.
5. Н. Дершовиц; Ж.-П. Jouannaud (1990). Ян ван Леувен (ред.). Системы перезаписи. Справочник по теоретической информатике. B. Эльзевир. С. 243–320. Здесь: раздел 8.1, с.293
6. В. Дикерт; А.Дж. Дункан; А.Г. Мясников (2011). «Геодезические переписывающие системы и предгруппы». У Олега Богопольского; Инна Бумагина; Ольга Харлампович; Энрик Вентура (ред.). Комбинаторная и геометрическая теория групп: конференции в Дортмунде и Оттаве-Монреале. Springer Science & Business Media. п. 62. ISBN  978-3-7643-9911-5.

• Д. Кнут; П. Бендикс (1970). Дж. Пиявка (ред.). Простые задачи со словами в универсальных алгебрах (PDF). Pergamon Press. С. 263–297.
• Жерар Юэ (1981). «Полное доказательство правильности алгоритма завершения Кнута-Бендикса» (PDF). J. Comput. Syst. Наука. 23 (1): 11–21. Дои:10.1016/0022-0000(81)90002-7.
• С. Симс. «Вычисления с конечно определенными группами». Кембридж, 1994.
• Энн Хейворт и К. Венсли. "Переписывание протоколов и идентичности между соотносителями." Группы Сент-Эндрюс 2001 г. в Оксфорде. Vol. Я, 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Кембридж, 2003.

внешняя ссылка

• Вайсштейн, Эрик В. «Алгоритм завершения Кнута – Бендикса». MathWorld.