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

T(M\-<i,JU~> , где Л = </)<-,..., Si, ... (it2 )> , Т(М) . Если для некоторого и/£&- 11/леМ и 6 tW )= 0 , то T(lO)neM - Получили случай, аналогичный предыдущему. Цусть 6 t(W )^ l)l-0 , Заменим W элементом г(So- ^^7/, ■ где А такое, что для 0 ,-цО выполняется условие (a): Vj , N /ПNjtl>, - /7 Hj . Очевидно, формула З п - ,W onejU эквивалентна формуле '%n,T(Vfont~”l>,) t J l . п . -rtt/f Слово Ufa Г преобразуем: Wo t * ) . J ? atflW ,i 1 ) , где J t/i - t y i ? 6 t M ) - 0 . . Применим к \lf0n t переписывающий процесс T , в результате получим: T(W,nt '" ‘'V- Т(ЧГ,)Z ( t i = г tC/i lOrt-J,) I • Допустим, что W t ^ X i . Покажем, что в этом случае Vп , T(Wtn t . Пусть W i l l * 1 . Если W t4_QH j , то в силу выбора |/t Н HtOl * t W>/ при п>1 . Если Щ е . Ц Щ и -- I — 90 М с ( П Hj) XL Ф П Н • , то можно легко показать, что и в этом случае Г /Wo nt ) J М . Пусть \\W ,\\b 1 , тогда Щ в N имеет нормальную форму Wt -А /А г- A t > где А ,'( N ft , i - 1,1 . Если IIА( X l l g 1 , то , и в силу выбора l/f ПТ/Юо"t п>>1)\\ =n t- . Допустим, что W ,-A i.,,A i, t> 1 , HAtAill - А, то есть h/jt 4 Njt . Покажем, что в этом случае Действительно, допустим, что W имеет нечетную слоговую длину, то есть К / , 6 R' k ■ в ,' I ( : 2 к +1 . х * 1 • Тогда ^ tl-Л) = ЙГЛ 1 *| б'к(.й ) и слоги &, в (-м содержатся соответственно в сомножителях • Поэто­ му * 6 й(. 4 ) II -Z и nW, йГ,,.^)\\ >1 . Отсюда следует, что 1105 Wt/.j,) ... II »£ . Допустим, что 05 = 6 ,...в,вквг.,...бг, I z 2 к , 6 « t Nj t , Тогда в слове V - i '. h W a U ) слоги Bg/.ii,) , £>' k ,. j ,) принадлежат соответственно * 112