АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1990 г.

Поэтому в дальнейшем будем считать, что в рассматриваемой полугруппе не все определяющие слова удовлетворяют условию К ( 2 -) , а значит, полугруппа не имеет циклов. П. э . п. ЪС - Т, ~ ' 7~£ = V } переводящую слово U. в И , назовём минимальной, если не существует п. э . п. ^ = Л> ~ 1” Р, Рк * \ / при К < С . Приведённая сеть, построенная для данной мини­ мальной п. э . п ., является минимальной в том смысле, что не существует приведённой сети с меньшим числом граней, у кото­ рой меткой верхнего пути является ^ , а меткой нижнего V , ■®ЖА з , если система определяющих соотношений полу­ группы П не имеет циклов, то в минимальной приведённой сети для слов Zt , V над П метка каждого внутреннего реб­ ра является куском. ДОКАЗАТЕЛЬСТВО . Предположим, что существует внутреннее ребро в такое, что у М - Е не является кус­ ком. Поскольку в - внутреннее, то оно принадлежит некоторой' нижней дуге е. f a и некоторой верхней дуге I < f ( f i ) a r i • Тогда и поэтому Н = Г, Е Гг f r t Е Et =Л / - определяющие соотноше­ ния полугруппы. Тогда Е - не кусок лишь в том случае, если /7 3 /"j , П. = Ft, . Рассмотрим 2 случая. • I) Г, £ Л , Г2 s А . Тогда А/ — Н , иначе Е - кусок по нашему определению. Следовательно, в п. э. п ., для ко­ торой построена рассматриваемая сеть, имеется поворот [10 ] и сеть не минимальна (можно уменьшить количество её граней на две, если выбросить ребро £ и склеить между собой дуги и 2 ) (7 & Л (случай, когда Г, ? А , полностью симмет­ ричен). Тогда пути fa , f a непусты. Пусть ( е *) - началь­ ное ребро пути fa ( f \ ) . Ясно, что рёбра £ г и е\ имеют общую начальную вершину Н и не совпадают ( если бы они сов­ падали, то по построению сети вершина R плела бы степень 2 , а все такие вершины мы удалили). Так как У ( f a ) = У ( fa)> то метки y f € i ) и У ( начинаются с одной буквы. Но тогда, учитывая, что П - полугруппа без циклов, из доказательства теоремы 4 .4 [ в ] следует, что в рассматриваемой п. э . п. есть поворот и сеть опять не мининаяьна. Полученное противоречие доказывает лемму. Теперь, как и в лемме 2, рассмотрим переход от сети V, SJ r f при построении минимальной приведённой сети для равных 87