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

, нием, имеем: A t B iS t^ A in H u A =А*ц 5 < ч Ъ<м . г д е £ R И £ U < I /4 P-. Отсвда следуют другие утверждения лемш 7. З а м е ч а н и е . В доказанной лемме S t является мак- симальным_обиим началом определяющих слов SiKtM&iM H i-м И S i K i S t - i H t и максимальным общим концом определяю­ щих слов S t и R i ^ i - i R i S i , тан как в противном случае слово В или слово А было бы свободно приводимо. Цусть А и В R -приведенные слова. Посмотрим, к ка­ кому веду можно привести слово АВ при помощи свободных приведений и R -приведений. Применив к слову АВ до тех пор, пока это возможно,сво­ бодные приведения и сильные R. -приведения, по лемш 7 , по­ лучим свободно приведенное слово АсЬсС0 (Со ^ I / 4 R ) , к ко­ торому не применимо сильное R -приведение. Если зашняемая часть R -приведения слова АиСсВс затрагивает одновременно и Ас и Ьс , то включим это R -приведение в число ужв про­ веденных, тогда Сс С 1 /2 R . Таким образом, получаем свобод­ но приведенное слово (1 ) АоСоЬс ( Со С 1/2 Ю , ГДв либо <Х^ I и тогда АоВс - R -приведено, либо С0 непус­ тая замещающая часть последнего R -приведения, причем R - приведения слова ( I ) , если возможны, не могут затронуть од­ новременно и Ас и Во . Пусть ( I ) - R -приводимо и, для определенности, R -при­ ведение затрагивает Ьо , Обозначим через С1 максимальное начало С0 , незатронутое R -приведением, а через С2 - конец Со , захваченный R -приведением. Применив в слову С0Е>о R -приведения, согласно лемш 6 , слева направо сколь­ ко это возможно, получим свободно приведенное слово ( 2 ) Wm-1 it » ( i w ^ - l ) , где 0 ,Ц лИ2 — Hm- iHmBm - R -приведено, I ( 1 4 й т > 1 /4 R . Дальнейшее рассмотрение возможных R -приведений разо­ бьем на случая в зависимости от возможности R -приведения - 23