АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

приведено, а ЕсЕи... Ек -1 Бк - R-приведено, причем Вк > 1/4 R, проведем, если возможно, К+1- е R -приве­ дение слова ЕоЕ^ ...Екм Вк Вк . В силу лемш 4 тог­ да имеем ЕсЕ< . . . Ек-^РкЬк~ЕоЕу -ЕкчЕкТХE>^BkM~*~ ж ЕоЕ^...Ek-iEkDkM Ь к *1 » где Dk ^ I/4R, Е к ^ I , В'к^- 1 / 2 R , как часть R -приведенного слова В , a B k > I / 4 R . По лемш 3 слово EoE i . . . Ек чЕкВкмЗ км - свободно приведено и по лемме 5 слово EoE-i ...Е к чЕ кВ км - R -приведено, что заканчивает доказательство лемш 6 . Л е м м а 7 . Если А и В являются R -приведенными словами и в преобразовании А В применяются только св о ­ бодные приведения и R -приведения сильные, то A - AmHm Hm -1 ••• ЕЦ , Ь = К, К2 . . . KmBm и последователь­ ные преобразования АЪ возможны только в следующем поряд­ ке: А В - AoB>= А < 8 Д = А2&.г&2= ••• = AmSrnBm» где А {-+ = A i H i , b i - i - K i B i , & «-I/4R, f c / s i , H i # I , К ;.* I и либо Ил.St i R+Oi £ R и тогда H^?-I/4R либо fU>I/4R, либо Rt®Ki (t= I , . . . , m). Д о к а з а т е л ь с т в о . Докажем индукцией по коли­ честву проведенных преобразований. Цусть уже проведено i преобразований (Ч = 0 , 1 , 2 , . . . ) , то есть получили Ai StBi , где Ai - начало А , Ъ-i - конец В и S i <- 1 /4 R . Сле­ дующее i + I - е преобразование может быть свободным приве­ дением лишь в том случае, когда S i - I , так как в против­ ном случае по лемш 3 слово A iS iB i свободно приведено. Т а -о ким образом, если i +1 - е преобразование есть свободное приведение, то A i S i B i s AtBi s Ai*iHi+iKt+<BiHs —A ih HinHiMBiH = Atи B in —AinSinBiiM , 8i*-i 4, 4. Пусть i +1 - e преобразование е сть сильное R -приведе­ ние. Так как Ai и B i являются R -приведенными как части R - приведенных А и В , й S i i I / 4 R , то заменяемая часть i + I - го сильного R -приведения должна захватить непустой конец A i,S i и непустое начало . Обозначив через £>t M замещающую часть этого \ +1 -приведения, через -к он ец At , k t ч - начало {ч # захваченные данным R -при гед е-