Algebra3

4.3. Лемма о ромбе. Нам понадобятся некоторые понятия и результаты, которые можно сформулировать на языке теории графов.

Напомним, что ориентированным графом (оргафом) называется пара (V, E), где V — множество вершин, а E V × V — множество дуг. Инициальная степень вершины u — это число исходящих из нее дуг, т. е. мощность множества {v V | hu, vi E}. Вершина, инициальная степень которой равна нулю, называется терминальной. Множество всех терминальных вершин орграфа G обозначим через T (G).

Ориентированным путем или цепью в графе G = (V, E)

называется последовательность вершин	{u }n	(n N
	i i≥0
{0, ∞}) такая, что hui, ui+1i E при 0	≤ i < n.	Неориен-

тированный путь — это такая последовательность {ui}ni=0, ui V , что для любого 0 ≤ i < n либо hui, ui+1i E, либо hui+1, uii E. Длиной (не)ориентированного пути {ui}ni=0 называется число n входящих в него дуг.

Для двух вершин u, v V говорим, что существует цепь из u в v (или что u и v связаны), если найдется конечная цепь (конечный неориентированный путь) {ui}ni=0 такая, что u0 = u, un = v. Отношение связности в этом смысле является эквивалентностью на V . Классы эквивалентных вершин называются компонентами связности графа G (рассматриваемого как неориентированный граф).

Определение 4.6. Орграф G = (V, E) называется переписывающим, если ни для какой вершины u V не существует бесконечной цепи с началом в вершине u.

Для любой вершины u переписывающего орграфа G определено непустое множество TG (u), состоящее из таких t T (G), для которых существует цепь из u в t. Заметим, что TG (u) = u тогда и только тогда, когда u T (G).

Определение 4.7. Назовем пару вершин hu, vi графа G

тривиальной, если TG (u) ∩ TG (v) 6= .

Определение 4.8. Переписывающий орграф G = (V, E) называется конфлюэнтным, если любая компонента связности содержит единственную терминальную вершину.

91

Предложение 4.9. Орграф G = (V, E) конфлюэнтный то- гда и только тогда, когда G — переписывающий и |TG (u)| = 1 для любой вершины u V .

Доказательство. Пусть G — конфлюэнтный орграф. Тогда для любой u V любые две вершины t1, t2 TG (u) связаны, т. е. лежат в одной компоненте связности. Следо-

вательно, t1 = t2.

Обратно, пусть G — такой переписывающий орграф, что |TG (u)| = 1 для любой вершины u V . Допустим, что существуют две различные терминальные вершины t1, t2 T (G), связанные конечным неориентированным путем {ui}ni=0, n ≥ 1, t1 = u0, t2 = un. Выберем наибольшее m {0, . . . , n} такое, что существует цепь из um в t1.

Ясно, что 1	≤ m ≤ n − 1. Так как цепи из um+1	в t1	нет,
hum, um+1i E. Поэтому TG (um+1) TG (um) =		{t1},	что
невозможно,	так как не существует цепи из um+1 в t1.

На любом конфлюэнтном орграфе G = (V, E) определена функция τ : V → T (G), которая каждой вершине u V ставит в соответствие ту единственную вершину t = τ(u) T (G), для которой существует цепь из u в t.

Лемма 4.10. Пусть G = (V, E) — переписывающий орграф. Тогда G конфлюэнтный в том и только том случае, когда выполнено следующее условие: для любой вершины u V и для любых дуг hu, v1i, hu, v2i E существуют вершина w V и цепи из v1 в w и из v2 в w.

Данный критерий конфлюэнтности известен под названием леммы о ромбе (Diamond Lemma). Графически его можно представить следующим образом.

92

Доказательство. Если G — конфлюэнтный орграф, то условие ромба, очевидно, выполнено: если hu, vi E, то TG (v) TG (u), поэтому достаточно рассмотреть w = τ(u) =

τ(v1) = τ(v2).

Обратно, предположим, что найдется вершина u V такая, что TG (u) t1, t2, t1 6= t2. По индукции построим последовательность вершин un V , n ≥ 0, обладающую следующим свойством:

1)|TG (un)| ≥ 2 при n ≥ 0;

2)для всех n ≥ 0 существует цепь положительной длины

из un в un+1.

Положим u0 = u. Для n > 0 по предположению индукции считаем, что вершина un−1 найдена. Выберем две различные

вершины t1, t2 TG (un−1). Рассмотрим цепь {vi}mi=0 из un−1 в t1.

Множество всех номеров i = 0, . . . , m таких, что существует цепь из vi в t2, непусто: v0 = un−1 лежит в этом множестве. Выберем максимальный индекс i из этого множества. Очевидно, i < m, так как вершина vm = t1 терми-

нальная, а t2 6= t1.

Рассмотрим цепь (ее длина положительна, поскольку vi

не может быть терминальной) из vi в t2 и первую дугу этой

цепи hvi, vi′+1i E.

Если |TG (vi′+1)| > 1, то положим un = vi′+1.

Случай |TG (vi′+1)| = 1 невозможен, поскольку по условию ромба существуют цепи из vi+1 и vi′+1 в некоторую вершину w. При этом TG (w) = {t2}, поэтому существует путь из vi+1 в t2, что противоречит выбору вершины vi+1.

93

Существование такой последовательности un, n ≥ 0, противоречит отсутствию бесконечных цепей в орграфе G.

4.4. Переписывающие системы. Пусть заданы мно-

жества X 6= и S X × X По указанным исходным данным построим орграф G = G(X, S) = (V, E) следующим образом. Множество вершин V этого орграфа совпадает с X . Две вершины u и v соединены дугой hu, vi E тогда

и только тогда, когда существуют слова w, w′ X# и пара hp, qi S такие, что u = wpw′ и v = wqw′.

Лемма 4.11. Если в орграфе G(X, S) существует цепь длины n из u в v, то для любых w1, w2 X# вершины w1uw2 и w1vw2 также соединены цепью, длина которой не превосхо- дит n.

Доказательство. Для n = 1 утверждение очевидно. Для n > 1 оно легко доказывается индукцией по длине цепи.

Определение 4.12. Множество S X × X называется

(конфлюэнтной) переписывающей системой на X , если ор-

граф G(X, S) переписывающий (конфлюэнтный). Слова в алфавите X, соответствующие терминальным вершинам орграфа G(X, S), называются редуцированными относительно S.

Теорема 4.13. Пара слов hu, vi X × X лежит в кон- груэнции θS тогда и только тогда, когда вершины u и v соединены в орграфе G(X, S) неориентированным путем.

Доказательство. Пусть E — множество дуг графа G = G(X, S). Заметим, что если hp, qi E, то hp, qi θS . Отсюда очевидно, что если две вершины u и v соединены неориентированным путем, то hu, vi θS .

94

Обратно, пусть hu, vi θS . По следствию 4.4 θS = θ(J), J — идеал алгебры A , порожденный множеством S+. Таким образом, элемент u + v J можно представить в виде

(4.3):

n
Xi	(u + v )w′	, n ≥ 0, w	, w′	X#, hu , v i S
u + v = w
i	i i i	i	i	i i
=1

(здесь мы унифицировали все суммы из (4.3), используя пустое слово). Раскрывая скобки, получаем выражение

Xn

u + v = (pi + qi), pi = wiuiwi′, qi = wiviwi′, hpi, qii E.

i=1

Повторяя рассуждения, использованные при доказательстве предложения 4.3(4), легко показать, что либо u = v, либо u и v соединены неориентированным путем.

Теорема 4.14. Пусть орграф G(X, S) конфлюэнтный. Образы слов u, v X в SmghX | Si равны тогда и только тогда, когда τ(u) = τ(v).

Доказательство. Пусть τ(u) = τ(v). Тогда, очевидно, существует ориентированный путь из u в v.

Обратно, пусть u и v соединены неориентированным путем. Проведем индукцию по длине n этого пути. Если n = 0 то u = v и утверждение тривиально. Если n = 1, то u и v соединены дугой, поэтому τ(u) = τ(v). Если n > 1, то рассмотрим вершину u1 V такую, что u и u1 соединены дугой, а u1 и v — неориентированным путем длины n − 1. По предположению индукции τ(u) = τ(u1) = τ(v).

Таким образом, носитель полугруппы SmghX | Si — это множество классов эквивалентных слов из X относительно конгруэнции θS , которые по теореме 4.13 совпадают с компонентами связности графа G(X, S). Следовательно, чтобы доказать, что образы слов u и v в фактор-полугруппе SmghX | Si различны, необходимо доказать, что не существует неориентированного пути, соединяющего вершины u и v.

95

Если S конфлюэнтна, то в каждой компоненте связности содержится ровно одна терминальная вершина, которую можно выбрать в качестве канонического представителя соответствующего класса эквивалентных слов. Поэтому из теоремы 4.14 вытекает, что в этом случае существует взаимнооднозначное соответствие между элементами SmghX | Si и редуцированными относительно S словами из X .

4.5. Лемма о композиции. Как прежде, X — непу-

стое множество, hu1, v1i, hu2, v2i X × X .

Определение 4.15. Пара hu, vi называется композицией пересечения hu1, v1i с hu2, v2i, если найдутся такие w, u′1, u′2 X , что

u1 = u′1w, u2 = wu′2, u = v1u′2, u = u′1v2, v = v1u′2.

Пара hu, vi называется композицией включения пары hu1, v1i

в hu2, v2i, если найдутся такие w1, w2 X#, что

u2 = w1u1w2, u = w1v1w2, v = v2.

Пусть S — переписывающая система на X . Легко видеть, что любая композиция любых пар из S лежит в конгруэнции, порожденной множеством S.

Теорема 4.16. Переписывающая система S конфлюэнтна тогда и только тогда, когда любая композиция любых двух пар из S тривиальна в орграфе G(X, S).

Доказательство. Пусть переписывающая система S конфлюэнтна. Проверим, например, что любая композиция пе-

ресечения пар из S тривиальна. Пусть hpi, qii S, i = 1, 2,

p1 = p′1w, p2 = wp′2, p′i, w X . Тогда для u = p′1wp′2 най-

дутся дуги hu, v1i, hu, v2i E, где v1 = p′1q2, v2 = q1p′2. Пара hv1, v2i является композицией пересечения hp1, q1i с hp2, q2i, ее

тривиальность вытекает из условия ромба.

Обратно, пусть все композиции пар из S тривиальны. Проверим условие ромба для орграфа G(X, S) (см. лемму 4.10). Пусть u, v1, v2 X , hu, v1i, hu, v2i E. Это означает, что

u = u′1p1u′′1 = u′2p2u′′2

96

для некоторых u′i, u′′i X#, hpi, qii S, i = 1, 2. При этом v1 = u′1q1u′′1, v2 = u′2q2u′′2 .

Возможны следующие три случая:

1. Вхождения подслов p1 и p2 в слово u не пересекаются: u = u′1p1u′p2u′′2, u′′1 = u′p2u′′2, u′2 = u′1p1u′, u′ X#.

В этом случае v1 = u′1q1u′p2u′′2, v2 = u′1p1u′q2u′′2 . Очевидно,

что hv1, wi, hv2, wi E, где. w = u′1q1u′q2u′′2 X

2. Вхождения подслов p1 и p2 в слово u пересекаются по подслову w X :

p1 = p′1w, p2 = wp′2,

u = u′1p′1wp′2u′′2, u′′1 = p′2u′′2 , u′2 = u′1p′1.

В этом случае v1 = u′1q1p′2u′′2, v2 = u′1p′1q2u′′2 . Существует композиция пересечения hp1, q1i с hp2, q2i, которая по усло-

вию тривиальна. Эта композиция равна hp′1q2, q1p′2i, следовательно, для некоторой вершины w существуют цепи из p′1q2 в w и из q1p′2 в w. По лемме 4.11 существуют цепи из v1 = u′1q1p′2u′′2 в u′1wu′′2 и из v2 = u′1p′1q2u′′2 в u′1wu′′2.

3. Вхождение подслова p1 в слово u является подсловом для соответствующего вхождения подслова p2:

p2 = w1p1w2, u′1 = u′2w1, u′′1 = w2u′′2, wi X#.

Этот случай рассматривается по аналогии с предыдущим.

Определение 4.17. Пусть A SmghX | Si — представление полугруппы при помощи порождающих элементов и определяющих соотношений. Тогда конфлюэнтная переписывающая система S′ такая, что θS = θS′ , называется базисом Гр¨ебнера — Ширшова полугруппы A относительно X.

Предложение 4.18. Пусть A — полугруппа, порожденная не более чем счетным множеством X Если найдется такой базис Гр¨ебнера — Ширшова S полугруппы A относительно X, что множество

˜			}
S = {p X		| hp, qi S для некоторого q X

97

рекурсивно, то проблема равенства для полугруппы A ал- горитмически разрешима.

Доказательство. Действительно, в этом случае легко построить алгоритм, вычисляющий функцию τ на вершинах орграфа G(X, S). Для данного слова u X множество всех его подслов конечно. Перебираем все такие подслова и

проверяем их на принадлежность к множеству ˜ Если все

S.

	˜
подслова слова u не лежат в S, то u T (G) и, следовательно,
τ(u) = u.	˜
	Если некоторое подслово p слова u лежит в S, то

найдем подходящее q X такое, что hp, qi S (это можно сделать, поскольку X счетное), и получим слово v X

такое, что hu, vi E(G). Заметим, что n(v) = n(u) − 1.	По
индукции находим τ(v) = τ(u).

Рассмотрим несколько примеров базисов Гр¨ебнера — Ширшова.

Пример 4.19. Пусть X0 = X {e}, e / X, S = Se(X) = {hee, ei} {hxe, xi, hex, xi | x X} X0 × X0 .

Очевидно, что S — переписывающая система (переход по дуге графа G(X0, S) уменьшает длину слова). Кроме того, легко проверить, что все композиции всех пар множества S тривиальны.

Следовательно, множество T (G(X0, S)) = X {e} явля-

ется носителем полугруппы SmghX0 | Si.
X ∩ X = , e / X X.			e	e	X},
Пример	4.20. Пусть		Y = X X	{e}, X = {x˜ | x
S0( e) =	˜	˜e	Рассмотрим
X	{hxx, ei, hxx, ei | x X} {hye, yi, hey, yi | y Y }.
					(4.4)
Множество S0 = S0(X) является конфлюэнтной переписы-
вающей системой.		Редуцированные относительно S0			слова

e

имеют вид u = e или u (X X) , где u не содержит подслов xx˜ и xx˜ , x X.

Ниже мы покажем, что полугруппа SmghY | S0(X)i является группой, изоморфной свободной группе, порожденной множеством X.

98

Теорема 4.16 позволяет также построить процедуру, которую можно применять для решения проблемы равенства в полугруппах. Суть этой процедуры состоит в пополнении множества S нетривиальными композициями пар из S. При этом необходимо следить, чтобы пополненная система определяющих соотношений оставалась переписывающей.

Напомним, что полугруппа A называется вполне упорядоченной, если на множестве A указано отношение ≤ такое, что (A, ≤) — вполне упорядоченное множество и для любых u, v, w A из u ≤ v следует wu ≤ wv и uw ≤ vw.

Пусть X — некоторое непустое множество. Отношение ≤ на множестве X назовем мономиальным порядком, если свободная полугруппа SmghXi относительно ≤ вполне упорядочена.

Пример 4.21. Пусть (X, ≤) — вполне упорядоченное множество. Определим порядок на множестве слов X следующим образом. Пусть даны два слова

u = x1 . . . xn, v = y1 . . . ym.

Положим u < v в том и только том случае, если n < m или n = m и при этом существует i {1, . . . , n} такое, что xi < yi

и xj = yj для всех j < i.

Это правило определяет отношение мономиального порядка на X , обозначаемое ≤deg-lex (слова сравниваются сперва по длине, а затем лексикографически).

Пример 4.22. Пусть X = X1 X2, X1 ∩ X2 = . Допустим, что на множестве слов X1 задан мономиальный порядок, а множество X2 вполне упорядочено. Оба этих отношения порядка будем обозначать одним символом ≤.

Определим мономиальный порядок на множестве X = (X1 X2) следующим образом. Любое слово u X можно единственным образом представить в виде

u = u x u . . . u x u		, u X#, x		i	X
1 1 2	n n n+1	i	1		2

(выделить буквы из X2), т. е. u — слово в алфавите Z = X1 X2. Упорядочим множество Z, полагая, что любой элемент из X2 больше любого элемента из X1 . Продолжим

99

это упорядочение на Z по правилу deg-lex. Построенное отношение называется башенным порядком.

Оевидно, что если на множестве X определен мономиальный порядок ≤, то любая система S X × X такая, что u > v для hu, vi S, является переписывающей. Дествительно, если в орграфе G(X, S) существует дуга из hp, qi, то p > q. Поэтому бесконечная цепь соответствовала бы бесконечной убывающей последовательности.

Допустим, что S X ×X — некоторая система определяющих соотношений. Зафиксируем мономиальный порядок ≤ на множестве X . Без ограничения общности можно считать, что u > v для любой пары hu, vi S. По индукции построим последовательность множеств Sn, n ≥ 0, следующим образом. Положим S = S0. Для n > 0, если все композиции всех пар множества Sn−1 тривиальны в Gn = G(X, Sn−1), то процесс закончен: Sn−1 — искомая система. В противном случае найдем все возможные нетривиальные компози-

ции всех пар из Sn−1.			Для каждой такой композиции hu, vi
выберем произвольно p TGn (u),					q TGn (v). Построим Sn,
добавив к Sn−1		все такие пары hp, qi (для p > q) или hq, pi
(для p < q).		S			(
G(X, Sn)	¯
Положим S		=	Sn.	Орграф G(X, S) получается из
		n≥0
	добавлением ряда новых дуг при этом компоненты
связности не меняются).				Поэтому пары вершин, тривиаль-
ные в G(X, Sn),					¯
		останутся тривиальными в G(X, S). Отсюда
					¯
очевидна конфлюэнтность переписывающей системы S. Сле-
	¯				— Ширшова полугруппы
довательно, S — базис Гребнера¨

SmghX | Si.

Для построения конфлюэнтных переписывающих систем в конкретных задачах целесообразно руководствоваться следующими правилами:

•если композиция hu, vi включения hu1, v1i в hu2, v2i тривиальна, то можно исключить hu2, v2i из множества определяющих соотношений;

•если композиция hu, vi включения hu1, v1i в hu2, v2i нетривиальна, то можно заменить hu2, v2i на hu, vi.

100