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

A ic >C4C2 S , . Таким образом, пришли к случаю, аналогичному I , с зашной Ао на Ан , а Со - на и с той лишь разни­ цей, что R -приведение ( I ) проводим сначала не с л еш напра­ в о, а справа налево. _ Случай 2 .2 .2 .2 . ]Во1<.|~П , то есть I — E>0 , С2 — S 2T-| t где T * I . _ _ _ _ _ Таким образом, QBcC2 —Q T T ^ i S 2 - Q T S 2 —фБ сЛдйр и д 0 с 0Б о ^ а , а / о С н Д 2 т , к в <— а Х с Л в < — . Согласно леммэ 3 слово A^S<T(BLb.; с в о ­ бодно приведено. Покажем, Ч' о A^T -iBCB -t может быть по- лучено из Ас С0Во при помощи одного R -приведения. |А о S 2 1> \ , так как | |>■ I S 2 ) . R -приведёние слова А 1 AoCiSgT, Ь с В -1 при помощи определяющего слова ApC^SgS^ не может затрагивать , так как в против­ ном случае S< и Т , ишют непустое общее начало, что про­ тиворечит свободной приведенности слова A ^ S ^B oB -t . Та­ ким образом, АпСоВо - А ч А о С ^ р . т Ж Р ц — "" A-iS’JV .bc'Bi и, аналогично случаю 2 .2 .2 .1 , приходим к случаю I с зашной Ъ с на Т,Е*ТЬ.,. Получили, что если А и Ъ R - приведены, то при помощи свободных приведений и сильных, и слабых R -приведений сло­ во ДЬ можвт быть преобразовано к одному из видов ( I ) - ( 4 ) , причем каждое из них R -приведено и только C l) может быть п у сто. Учитывая лемму 7 , можем сформулировать следующее сл ед ст­ вие. Л е м м а 8 . ЕсЛи А и В R -приведенные слова и АВ>=1, то слово АВ может быть преобразовано в пустоцу при помощи одних только свободных приведений и сильных R -приведений, то е сть существует целое t > 0 , суврствуют 1 ^ И р а А к при р * I , 2 , . . . , t такие, что шполняются следую- щ:га условия; A~HtHfc-< ...Н1 и В - K^Kg... K-fc , при р = 1 ,2 ..........± всегда либо Нр-Кр, либо Hp2p-iKpZp®Rp6 R с Z p -4 1 / 4 k , . 2 p f I / 4 R , H p > I / 4 R или K p > I / 4 R . Сохранив обозначения лемш 8 , введем следующие термины. - 26 -