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

вол D ; будет обозначать множество областей диаграммы Л/, имеющих мини­ мально возможное к внутренних и т внешних (граничных) рёбер. Граница кар­ ты Л/, области D - дМ, 3D. Метка области читается по часовой стрелке, а метка Л-диаграммы против часовой стрелки. Функцию метки обозначим через tp. Лемма 1. Пусть reR и r*eR, причём г шг\г2, г* = г2Г\ и г г г*: гхгг= r2rt. Тогда существует слово и такое, что гх = / , r 2 - sq, г = ,f*q,p+q >1. Определение I. Рассмотрим диаграмму М. Область D с Л/ называется де­ повской, если 1) ЗДпЗЛ /- последовательная часть ЗА/; 2) i(D) €{0, 1}. Определение 2. В слове v есть R-сокращение, если существует reR такое, ,.г а г что 1 ) либо v = v/v 2 Vi, г = v2“' г 2 , || г 2 1 | =1 и в словах r2v3 нет свободных со­ кращений и Л-сокращение состоит в замене слова v словом vtr2v j; 2) либо v а vtv2v3, г = v2, слово V ,V ), возможно, сократимо в F=F(X), и тогда Л-сокращение состоит в замене слова v словом v,vj с последующей заменой последнего рав­ ным несократимым в F словом. Определение 3 [1]. Полосой в диаграмме А/ типа С(4)&Т(4) называется к поддиаграмма П = и Д со свойствами: 1) ЗДгтЭА/-связное множество; /-1 2) ЗПпдМ - последовательная часть границы ЗА/; 3) i(Dx) - ;'(Д) = 2; 4) если к> 2, то при т — 2 , . . . ,к - 1 i{Dm) = 3; 5) ЭДпЭД+i - ребро ( / =1, . . . , к-\); 6 ) ЭДпЗД = 0 при |/ -j\> 1. Определение 4 [1]. В слове v есть R -сокращение, если существуют слова г\, гг, . . . ,rk е R такие, что v = v 0 v , .. . vM , г, = r'rfr ? , ||r/|| > 2 (/= 1 ,k), П * r 'rjrjrj, ||r,-|| > 1 (j = 2 ,. .. Д -l), r 3= г2, г/нгД, 0 = 2 , . . . , A-l), v, = (г /)'1 и в словах vor,2, rk vk+i, r 2 r 23 ...rk нет свободных сокращений. Л-сокращение со­ стоит в замене слова v равным ему в группе G словом v„r, 2 r 23... г^ у**,. • . t Деновским областям соответствуют Л-сокращения, а полосам - Л -сокращения. 98