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

i, =ад.;n ад, /ж=ад n зд+ь l s i s s-i. Пусть в диаграмме M содержится области Д , делящие вершины которой v„ v,' являются концами пути у, = ЗД п у, тогда удаление у , вместе с областью Д будет соответствовать ^-преобразованию слова и>в полугруппе G * Дейст­ вительно в этом случае w = w, q>(y,) vv2, где ф(у,) = (аЬ)""1' и ф(ЗД \ у,) = (Ьа )"’"1' , поэтому после удаления у, слово wt ф(у,) w 2 перейдет в слово н'| (Ьа)"л vr2 , что соответствует в Gfat следующему преобразованию: ф(У,) И >2 = W | (яб)""“W 2 -» W, (Ья)”-*W 2 . Лемма 7. Пусть ЭА/= у5, где ф(у), ф(б )'1 eG*ab и пусть каждая область Д , 1 < /< 5 диаграммы М является граничной и не является простой для любого j, 1 <j<s, ЗД n ЗД+i = li (/, - ребро). Тогда существует область Д с М такая, что концы пути у,_= ЗД п у являются делящими вершинами Д . Доказате. 1 ьство. Заметим следующее свойство делящих точек. Если вершина v, = /ж п б, области Д —делящая, то вершина v,’= /,+1 п 6 /+| не являет­ ся делящей для области Д+,; аналогично, если v, = /,+1 п у,-- делящая точка для Д, то v'(+| it /ж п у,ч| не является делящей для Д ц . Допустим, что существует область Д с Мтакая, что концы пути 6 / = ЗД п 5 являются делящими вершинами области Д . Тогда у области Д .| либо гонцы У).\ являются делящими, либо v ‘j.\ = lj гл у,-.) и Vy.| = lj .| п 8 Я . Допус­ тим, что имеет место второй случай. Тогда у области Д .2 делящими будут вер­ шины у ,_2 = lj .2 п 5Я , v’у _2 = /я п у/_ 2 , либо концы уя и так далее. В результате ес­ ли у области Д делящими являются вершины V 2 = l\ п § 2 , v 2 ’ = /2 П у2, то у области D|: V| = 8 ) n yi и vi ’= /| n yi, то есть Vi, vt - концы yt. Допустим, что среди областей диаграммы М нет области Д , делящие вершины которой vt, v*’являются концами б*. Тогда предположим, что у облас­ тиД , делящими являются вершины V| = 8 i n yt и vt ’= б| n 1и у области Д -v 2 = /] п у2, v2' = /2 п б 2 и так далее; и наконец, если у области Д .| делящи­ ми являются вершины: vs.t = l,.2п y„t, v ).| = ls.\ п 8s.i, то у Д - vs = Д n у„ 143