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

щий f и JJi-< a , 6 ,...,d> , ,М И - произволь­ ные элементы S - , удовлетворяющие условию леммы. Очевидно, соот­ ношение UJ 1 M 1 Пи/гМ^Ф эквивалентно соотношению: 3 ueMi, Зт/бМг, iCruJ-VUfz . ( 10 ) Представим группу & в виде полупрямого произведения как указано в лемме 2 . Подгруппы Mi ,М г на множестве новых об­ разующих группы & будут иметь представление TIMi)=<Qa,bo>-jdo'>, T(JU 2 ) - <Bo>di>,...,C o> , причем JU 1 <=d И} . Допустим, что - 0 , тогда в силу равенства (10) d t!U Jt)-0 . Подейст­ вуем на обе части равенства (10) переписывающим процессом Т , получим TIWi)T(U) - W )T (U b ) , ZW) , TflC &), l(u ) ,T (v )tH . Предпо­ ложим, что каждое Г/ИУ;) , t -t ,2 , имеет наименьшую слоговую дли­ ну среди представителей класса смежности Т(Мг)Т/Щ)т(М,) , i - 1 ,L . Допустим, что II171£4)11 < / . Поскольку \\WCr,)Uu)\\^\\Zn/)T<tOt)\\-\ и слоговую длину Т!М/г) нельзя уменьшить, умножая слева на слова из М г , то II i m W s I . Если Т т ) £ NJ, , r/U/t ) 6 f / j K , T(V) 6 t i j \ , . Действительно, так как Г(и)бЛН; <Ni k ^ то из равенст­ ва К и /,)-l(V)Z(u/t ) i ( u ) '1 следует, что N j* . Таким обра­ зом, T(dti ) , Z(U/i)e N j , T(M,j < fi/jj, ТШг)ПN j-Щ^ на основании индук­ тивного предположения и леммы 14 можно эффективно выяснить, спра­ ведливо ли соотношение Т(гСГ,) ТШАП Т(Мг ) 11 ЬУг) - ф , Случай, ког­ да IIKUAllbf и IITZMeJlU/, невозможен. Допустим противное, тог­ да Т(*/,) = 6 f 6 s , где , 6 г и Z(ti/,)T(u) - T(v)T(U/t) . Из соотношений \\tM )T (u )\\* \\T (V )T (ltrt )\\ и U fv ) \\£ / следует, что II =1 . Поэтому, чтобы равенство Tlv/i)T(u)-Tnf)T(l^i) име- ло место в N , необходимо, чтобы Ttv)£/Jj\ , . Но тогда A t~ T (v )fi , где А е AA/j£ , то есть слоговую длину Ttw ,) мож­ но уменьшить, умножая слева на T tv ) e T (M e ) . Если НТ/И4)||> 1, ш*з£)(1 >1 , то, как И В предыдущем случае, можно показать, что 133