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

где i - j t i , если S=m , и i - j , если $Фт, h u - i '\ o 't , От­ сюда следует рекуррентная система соотношений: Лу=|8/Л^ а ■ f где - t h jj t ‘, tlmj i &n,hmj(bm, гДе SimjtUi, hi.Jrl -t hmj t , i г 1, m-1, ; слова Aihjjg>- несократимы в U-t . И3 данной системы непосредственно получаем, что л-s М г £ \& л Ь 4*1 Рассмотрим случай, когда Tflff) , T/v) - трансформы, то есть Т(гО) =Sot*'... { >,nkw t ... t * '{* ', Si - i /, W ) -4* i e'aKvt в ,, S'j =H , где 6L ( Sj) , i - D,m i , ( j ^ 0,$-l) - представители левых клас­ сов смежности Ч по modify (И по modUi3 ), КшеН , Kve H , *v4Vt‘f . Сопрягаем TtUf) и X(V) одновременно словом i - S e t g’ .получим V/, , if, ^Z~' t ( v ) I .Пусть Vi имеет представление: Vt -Soto'S, i Ч „ йг 1 1 4,Kr t'*1', ,i*'6o', где %t - i l &i - представители левого класса смежности Н по modify . Выясним, существует ли /» такое, что v f e H . Для этого проверим, найдется ли такое [1,£ 2 , что ( й 1/^ . На основании леммы 4 эта проблема алгоритмически разрешима. Пусть такое /it существует. Тогда i f f ’zSot^'&t... *l '..Se \ где , Siel/f, , . Теперь опреде­ ляем существование такого , что (в,., Л 6 ; ! , f e£ [f.it , , и так далее. Таким образом, через конечное число шагов выясняется, су­ ществует ли искомое /I . Если существует, то на основании индук­ тивного предположения можно эффективно выяснить, является ли подгруппа единичной. Остается рассмотреть случай, когда Т(Ш) , Z(v) не принадле­ жат Н и не являются трансформами. Допустим, что выполняется соотношение Т(UI)n' = Т(VJПе , Тогда можно считать, что Г(ЬСГ) , T(v) циклически несократимы и Tew) =/ f' S tt1*6г i taАа, V vU si.,, i 1 ‘ b't , где Si(Aj'j, / -<77,/-- ЯП ), ~ T?3