Переписывающие системы
По просьбе marina_p освещаю вопрос насчёт переписывающих систем.
Речь пойдёт о довольно простой, но полезной технике. Общая постановка задачи в вольной формулировке такая. Дано некоторое множество объектов и некоторый набор элементарных преобразований этих объектов. При каких условиях каждый объект при помощи этих преобразований может быть приведён к единственной нормальной форме?
Вопросы подобного типа возникают очень часто. Например, в теории групп или полугрупп нахождение нормальной формы даёт решение проблемы равенства слов. При построении свободных конструкций (свободные группы, свободные произведения, HNN-расширения) переписывающая техника позволяет осуществить задуманное при минимальном количестве довольно тривиальных проверок.
Главным техническим средством является так называемая Diamond Lemma, доказанная М. Ньюманом в начале 40-х годов XX века. Это довольно элегантное утверждение о графах. Надо заметить, что переписывающие системы часто понимаются в двух смыслах: в широком и в узком. В первом случае речь идёт о любых объектах и преобразованиях (rewrite systems). Во втором варианте рассматриваются преобразования слов (string rewriting systems). Я буду рассматривать более общий вариант, переходя ко второму как одному из применений. Надо заметить, что в англоязычной литературе есть довольно много монографий, посвящённых переписывающим системам. Среди специалистов по Computer Science круг людей, занимающихся этими вещами, довольно широк. В математической литературе на русском языке вопрос освещён довольно бедно (мне известны только отдельные статьи). Даже терминология пока что плохо приживается.
Я впервые узнал о переписывающих системах в 1993 году из статьи, автором которой был Craig Squier. Несмотря на простоту этой техники, я вряд ли могу назвать средство, которое оказалось бы для меня в такой степени полезным. Если раньше построение нормальных форм осуществлялось при помощи кустарных средств, то теперь появился единый "индустриальный" метод.
Итак, что же такое переписывающая система (в широком смысле слова)? Можно сказать, что это просто ориентированный граф, то есть граф, на каждом ребре которого задано одно из двух направлений. Никаких более ограничений нет: могут быть и петли, и кратные рёбра, и что угодно. Формальное же определение такое: переписывающая система -- это упорядоченная пара (Г, \to), где x \to y означает, что в Г имеется ориентированное ребро с началом в вершине x и концом в вершине y. Конечно, если мы знаем граф Г, то мы можем однозначно восстановить отношение \to на множестве его вершин. Внесение \to в сигнатуру объясняется тем фактом, что переписывающая система -- это не просто ориентированный граф, а это такой граф, у которого мы интересуемся отношением \to и его свойствами.
Здесь напрашивается аналогия с определением ряда. Каково наилучшее определение ряда (с моей точки зрения)? Плохо говорить о "бесконечной сумме", так как никто не знает, что это такое. Хотя ряд полностью определяется последовательностью своих членов, отождествление ряда с последовательностью очень неудобно. Фактически, ряд -- это такая последовательность, у которой мы интересуемся её последовательностью частичных сумм. Поэтому лучше всего формально определять ряд как упорядоченную пару последовательностей a_n (n=1,2,...) и S_n (n=0,1,2,...), где S_n=a_1+...+a_n для любого n (при n=0 сумма пуста, и S_0=0). Именно такое определение ряда даётся, например, в учебнике матанализа С. М. Никольского.
Итак, пусть имеется переписывающая система (Г,\to). Введём два новых бинарных отношения на множестве вершин графа: отношения T и ~. Первое отношение есть рефлексивное транзитивное замыкание отношения \to. То есть x T y означает, что от x к y можно пройти по стрелкам (включая случай x=y). Далее, ~ есть эквивалентное замыкание отношения \to. Иными словами, x ~ y означает, что от x к y можно пройти по рёбрам, даже если разрешается идти в направлениях, противоположным направлениям рёбер.
Дадим теперь определения наиболее важных свойств переписывающих систем.
1. Система (Г,\to) называется нётеровой (Noetherian, или terminating), если не существует бесконечных последовательностей вершин со свойством v_1 \to v_2 \to ... \to v_n \to ... . Это значит, что мы не можем бесконечно долго путешествовать по графу, идя по направлениям стрелок.
Объект v (вершина) называется приведённым, если не существует такого объекта w, что v \to w. Иными словами, из v нельзя выйти. Ясно, что в нётеровой переписывающей системе, стартуя в вершине u и путешествуя по стрелкам, мы по определению придём к некоторой приведённой вершине v. В последнем случае будем говорить, что v есть приведённая форма u. У любого объекта в нётеровой системе имеется хотя бы одна приведённая форма, причём таковых может быть много. Естественно поставить вопрос о том, когда приведённая форма будет единственной.
2. Система (Г,\to) называется конфлюентной (confluent), если для любых объектов x,y,z из условий x T y, x T z следует существование такого объекта w, что y T w, z T w. Это означает, что если двое вышли из одной вершины и прошли по стрелкам, то они всегда могут сойтись в некоторой вершине, идя далее по стрелкам.
Конфлюентность очевидным образом влечёт единственность приведённой формы. Таким образом, если переписывающая система является полной (complete), т.е. нётеровой и конфлюентной, то всякий объект v имеет в точности одну приведённую форму, которая будет обозначаться через [v]. Более того, справедливо такое утверждение: два объекта эквивалентны тогда и только тогда, когда они имеют одну и ту же приведённую форму. В обозначениях это выглядит так: x ~ y iff [x]=[y]. Часть ``if" совсем очевидна, а часть ``only if" легко доказывается индукцией по длине пути, соединяющем x и y в графе.
Какие условия могут гарантировать нётеровость и конфлюентность системы? В первом случае достаточно построить на множестве вершин графа некоторое отношение "меньше", удовлетворяющее условию обрыва убывающих цепей и такое, что из x \to y следует, что y меньше x. Например, если вершины графа -- это слова над некоторым алфавитом, то их можно упорядочить сначала по длине, а при равных длинах -- лексикографически (порядок ShortLex). При этом для обеспечения нётеровости достаточно того, чтобы при переходе от одного слова к другому по стрелке либо уменьшалась длина слова, либо она не менялась, но слово уменьшалось относительно порядка слов в словаре.
Проверка конфлюентности прямым способом намного сложнее, так как надо как-то следить за всеми парами путей, выходящими из одной вершины. Оказывается, в этом нет необходимости.
3. Система (Г,\to) называется локально конфлюентной, если если для любых объектов x,y,z из условий x \to y, x \to z следует существование такого объекта w, что y T w, z T w. Это означает, что если двое вышли из одной вершины, и каждый прошёл по одному направленному ребру, то они могут где-то сойтись, идя по стрелкам.
Ясно, что всякая конфлюентная система локально конфлюентна. Нетрудно построить примеры, когда обратное неверно. Однако имеет место следующее утверждение.
Diamond Lemma (M. Newman) Нётерова переписывающая система конфлюентна тогда и только тогда, когда она локально конфлюентна.
Доказательство является несложным, если использовать идею нётеровой индукции: если требуется доказать некоторое утверждение P для всех объектов нётеровой системы, то его достаточно доказать для произвольного объекта в предположении, что оно справедливо для всех "нисходящих" объектов. То есть мы должны доказать P(x) в предположении, что P(y) справедливо для любого объекта y, в который можно пройти из x по стрелкам, пройдя при этом хотя бы одну стрелку.
В качестве P(x) можно взять условие из определения конфлюентности. Если при этом выполнено x T y, x T z, то достаточно рассмотреть случай, когда пути по стрелкам от x к y и от x к z непусты (в противном случае имеем x=y или x=z, и доказывать нечего). Итак, рассмотрим первые рёбра путей, и пусть x \to y', y' T y, x \to z', z' T z. Рекомендуется нарисовать картинку со стрелками, которая в итоге будет иметь форму ромбика (откуда и происходит название леммы). Для начала применим условие локальной конфлюентности к паре рёбер x \to y', x \to z', находя такое v, что y' T v, z' T v. Далее, вершины y' и z' являются нисходящими по отношению к x, и то же относится к вершине v. Поэтому мы можем применить нётерову индукцию, используя утверждения P(y') и P(z'). При этом для y' T y и y' T v мы можем получить y'' такое, что y T y'', v T y''. Аналогично, для z' T z и z' T v получаем z'' такое, что z T z'', v T z''. Наконец, используем P(v), и из условий v T y'', v T z'' найдём w такое, при котором y'' T w, z'' T w. Ясно, что в силу транзитивности отношения T выполнены условия y T w, z T w, а это и требовалось доказать.
Закончить хотелось бы примерами применения этой техники для решения проблемы слов в группах и полугруппах. Я ограничусь случаем полугрупп, так как он проще для иллюстраций, а также потому, что к нему сводится и групповой случай: мы просто добавляем обратные буквы и соотношения вида xx^{-1}=x^{-1}x=1.
Итак, пусть мы имеем полугруппу (с единицей), заданную при помощи определяющих соотношений:
[ X | U_1=V_1, ..., U_n=V_n ], где X -- алфавит, U_i,V_i -- слова над этим алфавитом. Мы заранее можем задать на множестве всех слов некоторый порядок, удовлетворяющий условию обрыва убывающих цепей (например, описанный выше порядок ShortLex). При этом все соотношения можно записать так, что правые части будут меньше левых в смысле этого порядка. Теперь можно задать такую переписывающую систему: вершинами графа будут все слова над Х (включая пустое), а переходы (рёбра) будут соответствовать элементарным преобразованиям слов, т.е. заменам подслов вида U_i на слова V_i. Формально говоря, мы полагаем PU_{i}Q \to PV_{i}Q для любых слов P,Q и любого i=1,2,...,n.
В результате получается ориентированный граф Г, в котором вершины (слова) соединены тогда и только тогда, когда они задают одинаковые элементы полугруппы. Для решения проблемы равенства слов достаточно для каждого слова уметь находить нормальную форму, чтобы при этом слова были эквивалентны тогда и только тогда, когда их нормальные формы совпадают. Система (Г,\to) уже является нётеровой, поэтому достаточно иметь конфлюентность. Ввиду теоремы Ньюмана можно ограничиться локальной конфлюентностью. Последнее условие проверяется в явном виде.
Пусть мы имеем некоторую вершину (т.е. слово), из которой исходят две стрелки. Это значит, что мы применяем к слову два элементарных преобразования, заменяя некоторые его вхождения U_i,U_j на V_i,V_j соответственно. Если вхождения не перекрываются, то локальная конфлюентность не нарушается. Если же вхождения перекрываются, то возможно два случая: они могут или содержаться одно в другом (более редкий случай) или перекрываться по некоторому непустому слову. Без ограничения общности мы можем отсечь лишнее, рассматривая только ту часть нашего слова, которая есть объединение вхождений U_i,U_j. Проверке подлежат следующие два случая.
A. U_{i} имеет вид PQ, U_{j} имеет вид QR, где Q непусто. То есть мы имеем вершину PQR, от которой можно пройти по ребру как к слову V_{i}R, так и к слову PV_{j}. Производя преобразования в этих словах, мы хотим привести их к одному слову, т.е. найти такое W, что V_{i}R T W, PV_{j} T W.
B. U_{j} содержится в U_{i}, равном PU_{j}R. В этом случае от вершины U_{i} мы можем перейти по ребру как к V_{i}, так и к PV_{j}R. Целью является нахождение такого слова W, что V_{i} T W, PV_{j}R T W.
Как правило, эти проверки являются очень лёгкими. Рассмотрим несколько примеров.
1) [ a,b,c | ba=ab, ca=ac, cb=bc ]. Случай B здесь не может иметь места. Случай A возникает только в одной ситуации, когда левые части соотношений могут перекрываться: это слова cb и ba. Это приводит к рассмотрению одного слова cba, от которого можно перейти как к bca (cb \to bc), так и к cab (ba \to ab). Полученные нами слова bca, cab приводятся к одному и тому же слову abc, а именно: bca \to bac \to abc, cab \to acb \to abc. Таким образом, рассматриваемая система полна. Если нам надо выяснить, равны ли какие-то слова в данной полугруппе, то надо каждое из слов привести к нормальной форме. Это делается эффективно. Одно и то же слово можно приводить разными путями, но приведённая форма слова от этого не зависит. Далее остаётся только сравнить полученные приведённые формы.
2) [ x,y,z,X,Y,Z | xX=1, Xx=1, yY=1, Yy=1, zZ=1, Zz=1 ]. Это свободная группа ранга 3. Заглавные буквы -- это обратные элементы. Здесь возможно 6 случаев "перекрытия" соотношений, но все они однотипны. Скажем, рассмотрим слова xX и Xx, перекрывающиеся по X. Здесь мы имеем дело со словом xXx, в котором подслова xX и Xx заменяются на пустые. Результатом будет в обоих случаях слово x, т.е. дальше ничего можно не проверять. Это показывает, что последовательные сокращения рядом стоящих взаимно обратных букв всегда приводят к одному и тому же несократимому слову.
Заметим, что почти столь же просто построить на этом пути свободные произведения групп, а также свободные произведения с объединённой подгруппой. Это же относится к построению HNN-расширений.
3) [ a,b | baaba=a ]. Здесь слово всего одно, но оно перекрывается само с собой по ba. Склеивая два таких слова, перекрывающиеся по ba, мы приходим к проверке одного случая x=baabaaba. Из данной вершины исходят два ребра. Если мы заменим начало слова на a, то получим aaba. Если конец -- то получим baaa. Что дальше делать с этими словами? Оба они приведены, но не равны. То есть система не полна. Если бы мы этим и ограничились, то область применения переписывающей техники была бы очень и очень узка. Однако мы поступим так. Слова aaba и baaa эквивалентны исходному слову x, то есть они равны в полугруппе. Если мы добавим к имеющемуся соотношению ещё и равенство baaa=aaba, то отношение эквивалентности слов окажется неизменным. То есть если система оказалась неполна, мы её просто пополняем, переходя к [ a,b | baaba=a, baaa=aaba ].
Будет ли полной новая система? Этот факт снова подлежит проверке. Поскольку случай B по-прежнему невозможен, надо перебрать все варианты перекрытия слов. Таких вариантов всего два. Один из них старый, и его проверять не надо. Теперь слова aaba и baaa из предыдущего абзаца автоматически приводятся к aaba в новой системе. Но у нас есть новое соотношение, и потому возникло новое перекрытие: baaba перекрывается с baaa по ba. (Здесь надо всегда быть внимательным, так как новое слово может давать несколько новых перекрытий; два слова могут перекрываться не одним, а многими способами -- всё это надо проверять.) Итак, склеим наши перекрывающиеся слова как и выше, что приводит нас к y=baabaaa. Две стрелки, идущие из y, дают нам слова aaa (baaba \to a в начале слова) и baaaaba (baaa \to aaba в конце слова). Слово aaa приведено. Второе из слов не приведено, и мы его приводим: baaaaba = (baaa)aba \to aabaaba = aa(baaba) \to aaa. Всё сошлось. Новая система оказалась полной.
Процесс пополнения, который мы описали, носит название процедуры Кнута -- Бендикса. В нашем случае потребовался один шаг процедуры. В общем же случае могли возникнуть новые ситуации, когда локальная конфлюентность нарушается, и надо вводить всё новые и новые соотношения, что ведёт к проверке новых ситуаций. Иногда процесс оканчивается за конечное число шагов. Иногда он требует бесконечного числа шагов, при которых возникают, скажем так, однотипные соотношения. В этом случае можно воспользоваться индукцией, угадав вид того, что в итоге возникает.
Скажем, если бы мы ввели другое упорядочение на множестве букв, при котором b предшествует a, то мы пришли бы к системе соотношений baaba=a, aaba=baaa. Легко понять, что при этом возник бы случай B, рассмотрение которого привело бы к системе равенств bbaaa=a, aaba=baaa. При этом возникают случаи перекрытия слов bbaaa и aaba как по a, так и по aa. Один из случаев не даёт ничего нового, а второй приводит ещё к одному соотношению: bbabaaa=aba. Эта система вновь неполна. Процедура Кнута -- Бендикса здесь длится бесконечно, но все возникающие новые соотношения имеют вид bb(ab)^{m}aaa=a(ba)^m. Все они, взятые при m=0,1,2,... вместе с соотношением aaba=baaa, образуют уже полную систему.
Таким образом, ход процесса сильно может зависеть от выбранного упорядочения. Однако представляется довольно затруднительным понять сразу, какое из упорядочений будет лучше.
В заключение заметим, что переписывающие системы можно с эффектом применять и во многих других случаях -- например, для колец. Вообще, в любой ситуации, где возникают элементарные преобразования объектов, бывает полезно рассмотреть ту или иную переписывающую систему.
Речь пойдёт о довольно простой, но полезной технике. Общая постановка задачи в вольной формулировке такая. Дано некоторое множество объектов и некоторый набор элементарных преобразований этих объектов. При каких условиях каждый объект при помощи этих преобразований может быть приведён к единственной нормальной форме?
Вопросы подобного типа возникают очень часто. Например, в теории групп или полугрупп нахождение нормальной формы даёт решение проблемы равенства слов. При построении свободных конструкций (свободные группы, свободные произведения, HNN-расширения) переписывающая техника позволяет осуществить задуманное при минимальном количестве довольно тривиальных проверок.
Главным техническим средством является так называемая Diamond Lemma, доказанная М. Ньюманом в начале 40-х годов XX века. Это довольно элегантное утверждение о графах. Надо заметить, что переписывающие системы часто понимаются в двух смыслах: в широком и в узком. В первом случае речь идёт о любых объектах и преобразованиях (rewrite systems). Во втором варианте рассматриваются преобразования слов (string rewriting systems). Я буду рассматривать более общий вариант, переходя ко второму как одному из применений. Надо заметить, что в англоязычной литературе есть довольно много монографий, посвящённых переписывающим системам. Среди специалистов по Computer Science круг людей, занимающихся этими вещами, довольно широк. В математической литературе на русском языке вопрос освещён довольно бедно (мне известны только отдельные статьи). Даже терминология пока что плохо приживается.
Я впервые узнал о переписывающих системах в 1993 году из статьи, автором которой был Craig Squier. Несмотря на простоту этой техники, я вряд ли могу назвать средство, которое оказалось бы для меня в такой степени полезным. Если раньше построение нормальных форм осуществлялось при помощи кустарных средств, то теперь появился единый "индустриальный" метод.
Итак, что же такое переписывающая система (в широком смысле слова)? Можно сказать, что это просто ориентированный граф, то есть граф, на каждом ребре которого задано одно из двух направлений. Никаких более ограничений нет: могут быть и петли, и кратные рёбра, и что угодно. Формальное же определение такое: переписывающая система -- это упорядоченная пара (Г, \to), где x \to y означает, что в Г имеется ориентированное ребро с началом в вершине x и концом в вершине y. Конечно, если мы знаем граф Г, то мы можем однозначно восстановить отношение \to на множестве его вершин. Внесение \to в сигнатуру объясняется тем фактом, что переписывающая система -- это не просто ориентированный граф, а это такой граф, у которого мы интересуемся отношением \to и его свойствами.
Здесь напрашивается аналогия с определением ряда. Каково наилучшее определение ряда (с моей точки зрения)? Плохо говорить о "бесконечной сумме", так как никто не знает, что это такое. Хотя ряд полностью определяется последовательностью своих членов, отождествление ряда с последовательностью очень неудобно. Фактически, ряд -- это такая последовательность, у которой мы интересуемся её последовательностью частичных сумм. Поэтому лучше всего формально определять ряд как упорядоченную пару последовательностей a_n (n=1,2,...) и S_n (n=0,1,2,...), где S_n=a_1+...+a_n для любого n (при n=0 сумма пуста, и S_0=0). Именно такое определение ряда даётся, например, в учебнике матанализа С. М. Никольского.
Итак, пусть имеется переписывающая система (Г,\to). Введём два новых бинарных отношения на множестве вершин графа: отношения T и ~. Первое отношение есть рефлексивное транзитивное замыкание отношения \to. То есть x T y означает, что от x к y можно пройти по стрелкам (включая случай x=y). Далее, ~ есть эквивалентное замыкание отношения \to. Иными словами, x ~ y означает, что от x к y можно пройти по рёбрам, даже если разрешается идти в направлениях, противоположным направлениям рёбер.
Дадим теперь определения наиболее важных свойств переписывающих систем.
1. Система (Г,\to) называется нётеровой (Noetherian, или terminating), если не существует бесконечных последовательностей вершин со свойством v_1 \to v_2 \to ... \to v_n \to ... . Это значит, что мы не можем бесконечно долго путешествовать по графу, идя по направлениям стрелок.
Объект v (вершина) называется приведённым, если не существует такого объекта w, что v \to w. Иными словами, из v нельзя выйти. Ясно, что в нётеровой переписывающей системе, стартуя в вершине u и путешествуя по стрелкам, мы по определению придём к некоторой приведённой вершине v. В последнем случае будем говорить, что v есть приведённая форма u. У любого объекта в нётеровой системе имеется хотя бы одна приведённая форма, причём таковых может быть много. Естественно поставить вопрос о том, когда приведённая форма будет единственной.
2. Система (Г,\to) называется конфлюентной (confluent), если для любых объектов x,y,z из условий x T y, x T z следует существование такого объекта w, что y T w, z T w. Это означает, что если двое вышли из одной вершины и прошли по стрелкам, то они всегда могут сойтись в некоторой вершине, идя далее по стрелкам.
Конфлюентность очевидным образом влечёт единственность приведённой формы. Таким образом, если переписывающая система является полной (complete), т.е. нётеровой и конфлюентной, то всякий объект v имеет в точности одну приведённую форму, которая будет обозначаться через [v]. Более того, справедливо такое утверждение: два объекта эквивалентны тогда и только тогда, когда они имеют одну и ту же приведённую форму. В обозначениях это выглядит так: x ~ y iff [x]=[y]. Часть ``if" совсем очевидна, а часть ``only if" легко доказывается индукцией по длине пути, соединяющем x и y в графе.
Какие условия могут гарантировать нётеровость и конфлюентность системы? В первом случае достаточно построить на множестве вершин графа некоторое отношение "меньше", удовлетворяющее условию обрыва убывающих цепей и такое, что из x \to y следует, что y меньше x. Например, если вершины графа -- это слова над некоторым алфавитом, то их можно упорядочить сначала по длине, а при равных длинах -- лексикографически (порядок ShortLex). При этом для обеспечения нётеровости достаточно того, чтобы при переходе от одного слова к другому по стрелке либо уменьшалась длина слова, либо она не менялась, но слово уменьшалось относительно порядка слов в словаре.
Проверка конфлюентности прямым способом намного сложнее, так как надо как-то следить за всеми парами путей, выходящими из одной вершины. Оказывается, в этом нет необходимости.
3. Система (Г,\to) называется локально конфлюентной, если если для любых объектов x,y,z из условий x \to y, x \to z следует существование такого объекта w, что y T w, z T w. Это означает, что если двое вышли из одной вершины, и каждый прошёл по одному направленному ребру, то они могут где-то сойтись, идя по стрелкам.
Ясно, что всякая конфлюентная система локально конфлюентна. Нетрудно построить примеры, когда обратное неверно. Однако имеет место следующее утверждение.
Diamond Lemma (M. Newman) Нётерова переписывающая система конфлюентна тогда и только тогда, когда она локально конфлюентна.
Доказательство является несложным, если использовать идею нётеровой индукции: если требуется доказать некоторое утверждение P для всех объектов нётеровой системы, то его достаточно доказать для произвольного объекта в предположении, что оно справедливо для всех "нисходящих" объектов. То есть мы должны доказать P(x) в предположении, что P(y) справедливо для любого объекта y, в который можно пройти из x по стрелкам, пройдя при этом хотя бы одну стрелку.
В качестве P(x) можно взять условие из определения конфлюентности. Если при этом выполнено x T y, x T z, то достаточно рассмотреть случай, когда пути по стрелкам от x к y и от x к z непусты (в противном случае имеем x=y или x=z, и доказывать нечего). Итак, рассмотрим первые рёбра путей, и пусть x \to y', y' T y, x \to z', z' T z. Рекомендуется нарисовать картинку со стрелками, которая в итоге будет иметь форму ромбика (откуда и происходит название леммы). Для начала применим условие локальной конфлюентности к паре рёбер x \to y', x \to z', находя такое v, что y' T v, z' T v. Далее, вершины y' и z' являются нисходящими по отношению к x, и то же относится к вершине v. Поэтому мы можем применить нётерову индукцию, используя утверждения P(y') и P(z'). При этом для y' T y и y' T v мы можем получить y'' такое, что y T y'', v T y''. Аналогично, для z' T z и z' T v получаем z'' такое, что z T z'', v T z''. Наконец, используем P(v), и из условий v T y'', v T z'' найдём w такое, при котором y'' T w, z'' T w. Ясно, что в силу транзитивности отношения T выполнены условия y T w, z T w, а это и требовалось доказать.
Закончить хотелось бы примерами применения этой техники для решения проблемы слов в группах и полугруппах. Я ограничусь случаем полугрупп, так как он проще для иллюстраций, а также потому, что к нему сводится и групповой случай: мы просто добавляем обратные буквы и соотношения вида xx^{-1}=x^{-1}x=1.
Итак, пусть мы имеем полугруппу (с единицей), заданную при помощи определяющих соотношений:
[ X | U_1=V_1, ..., U_n=V_n ], где X -- алфавит, U_i,V_i -- слова над этим алфавитом. Мы заранее можем задать на множестве всех слов некоторый порядок, удовлетворяющий условию обрыва убывающих цепей (например, описанный выше порядок ShortLex). При этом все соотношения можно записать так, что правые части будут меньше левых в смысле этого порядка. Теперь можно задать такую переписывающую систему: вершинами графа будут все слова над Х (включая пустое), а переходы (рёбра) будут соответствовать элементарным преобразованиям слов, т.е. заменам подслов вида U_i на слова V_i. Формально говоря, мы полагаем PU_{i}Q \to PV_{i}Q для любых слов P,Q и любого i=1,2,...,n.
В результате получается ориентированный граф Г, в котором вершины (слова) соединены тогда и только тогда, когда они задают одинаковые элементы полугруппы. Для решения проблемы равенства слов достаточно для каждого слова уметь находить нормальную форму, чтобы при этом слова были эквивалентны тогда и только тогда, когда их нормальные формы совпадают. Система (Г,\to) уже является нётеровой, поэтому достаточно иметь конфлюентность. Ввиду теоремы Ньюмана можно ограничиться локальной конфлюентностью. Последнее условие проверяется в явном виде.
Пусть мы имеем некоторую вершину (т.е. слово), из которой исходят две стрелки. Это значит, что мы применяем к слову два элементарных преобразования, заменяя некоторые его вхождения U_i,U_j на V_i,V_j соответственно. Если вхождения не перекрываются, то локальная конфлюентность не нарушается. Если же вхождения перекрываются, то возможно два случая: они могут или содержаться одно в другом (более редкий случай) или перекрываться по некоторому непустому слову. Без ограничения общности мы можем отсечь лишнее, рассматривая только ту часть нашего слова, которая есть объединение вхождений U_i,U_j. Проверке подлежат следующие два случая.
A. U_{i} имеет вид PQ, U_{j} имеет вид QR, где Q непусто. То есть мы имеем вершину PQR, от которой можно пройти по ребру как к слову V_{i}R, так и к слову PV_{j}. Производя преобразования в этих словах, мы хотим привести их к одному слову, т.е. найти такое W, что V_{i}R T W, PV_{j} T W.
B. U_{j} содержится в U_{i}, равном PU_{j}R. В этом случае от вершины U_{i} мы можем перейти по ребру как к V_{i}, так и к PV_{j}R. Целью является нахождение такого слова W, что V_{i} T W, PV_{j}R T W.
Как правило, эти проверки являются очень лёгкими. Рассмотрим несколько примеров.
1) [ a,b,c | ba=ab, ca=ac, cb=bc ]. Случай B здесь не может иметь места. Случай A возникает только в одной ситуации, когда левые части соотношений могут перекрываться: это слова cb и ba. Это приводит к рассмотрению одного слова cba, от которого можно перейти как к bca (cb \to bc), так и к cab (ba \to ab). Полученные нами слова bca, cab приводятся к одному и тому же слову abc, а именно: bca \to bac \to abc, cab \to acb \to abc. Таким образом, рассматриваемая система полна. Если нам надо выяснить, равны ли какие-то слова в данной полугруппе, то надо каждое из слов привести к нормальной форме. Это делается эффективно. Одно и то же слово можно приводить разными путями, но приведённая форма слова от этого не зависит. Далее остаётся только сравнить полученные приведённые формы.
2) [ x,y,z,X,Y,Z | xX=1, Xx=1, yY=1, Yy=1, zZ=1, Zz=1 ]. Это свободная группа ранга 3. Заглавные буквы -- это обратные элементы. Здесь возможно 6 случаев "перекрытия" соотношений, но все они однотипны. Скажем, рассмотрим слова xX и Xx, перекрывающиеся по X. Здесь мы имеем дело со словом xXx, в котором подслова xX и Xx заменяются на пустые. Результатом будет в обоих случаях слово x, т.е. дальше ничего можно не проверять. Это показывает, что последовательные сокращения рядом стоящих взаимно обратных букв всегда приводят к одному и тому же несократимому слову.
Заметим, что почти столь же просто построить на этом пути свободные произведения групп, а также свободные произведения с объединённой подгруппой. Это же относится к построению HNN-расширений.
3) [ a,b | baaba=a ]. Здесь слово всего одно, но оно перекрывается само с собой по ba. Склеивая два таких слова, перекрывающиеся по ba, мы приходим к проверке одного случая x=baabaaba. Из данной вершины исходят два ребра. Если мы заменим начало слова на a, то получим aaba. Если конец -- то получим baaa. Что дальше делать с этими словами? Оба они приведены, но не равны. То есть система не полна. Если бы мы этим и ограничились, то область применения переписывающей техники была бы очень и очень узка. Однако мы поступим так. Слова aaba и baaa эквивалентны исходному слову x, то есть они равны в полугруппе. Если мы добавим к имеющемуся соотношению ещё и равенство baaa=aaba, то отношение эквивалентности слов окажется неизменным. То есть если система оказалась неполна, мы её просто пополняем, переходя к [ a,b | baaba=a, baaa=aaba ].
Будет ли полной новая система? Этот факт снова подлежит проверке. Поскольку случай B по-прежнему невозможен, надо перебрать все варианты перекрытия слов. Таких вариантов всего два. Один из них старый, и его проверять не надо. Теперь слова aaba и baaa из предыдущего абзаца автоматически приводятся к aaba в новой системе. Но у нас есть новое соотношение, и потому возникло новое перекрытие: baaba перекрывается с baaa по ba. (Здесь надо всегда быть внимательным, так как новое слово может давать несколько новых перекрытий; два слова могут перекрываться не одним, а многими способами -- всё это надо проверять.) Итак, склеим наши перекрывающиеся слова как и выше, что приводит нас к y=baabaaa. Две стрелки, идущие из y, дают нам слова aaa (baaba \to a в начале слова) и baaaaba (baaa \to aaba в конце слова). Слово aaa приведено. Второе из слов не приведено, и мы его приводим: baaaaba = (baaa)aba \to aabaaba = aa(baaba) \to aaa. Всё сошлось. Новая система оказалась полной.
Процесс пополнения, который мы описали, носит название процедуры Кнута -- Бендикса. В нашем случае потребовался один шаг процедуры. В общем же случае могли возникнуть новые ситуации, когда локальная конфлюентность нарушается, и надо вводить всё новые и новые соотношения, что ведёт к проверке новых ситуаций. Иногда процесс оканчивается за конечное число шагов. Иногда он требует бесконечного числа шагов, при которых возникают, скажем так, однотипные соотношения. В этом случае можно воспользоваться индукцией, угадав вид того, что в итоге возникает.
Скажем, если бы мы ввели другое упорядочение на множестве букв, при котором b предшествует a, то мы пришли бы к системе соотношений baaba=a, aaba=baaa. Легко понять, что при этом возник бы случай B, рассмотрение которого привело бы к системе равенств bbaaa=a, aaba=baaa. При этом возникают случаи перекрытия слов bbaaa и aaba как по a, так и по aa. Один из случаев не даёт ничего нового, а второй приводит ещё к одному соотношению: bbabaaa=aba. Эта система вновь неполна. Процедура Кнута -- Бендикса здесь длится бесконечно, но все возникающие новые соотношения имеют вид bb(ab)^{m}aaa=a(ba)^m. Все они, взятые при m=0,1,2,... вместе с соотношением aaba=baaa, образуют уже полную систему.
Таким образом, ход процесса сильно может зависеть от выбранного упорядочения. Однако представляется довольно затруднительным понять сразу, какое из упорядочений будет лучше.
В заключение заметим, что переписывающие системы можно с эффектом применять и во многих других случаях -- например, для колец. Вообще, в любой ситуации, где возникают элементарные преобразования объектов, бывает полезно рассмотреть ту или иную переписывающую систему.