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

образующие группы О- входят в l ( i ,—,C^ и 6 { ( l ) - 0 . Тогда G представима в виде HNN -группы: &= <с,Н) le tH , t ~1a t - Ш , Уа€1Г, > , где Ы ) --(/-< ;группа Н, подгруппы V \ , V-t и изоморфизм / , заданный на подгруппе LTt , определены выше. Обозначим через Т процесс, переписывающий слова в образующих { t i \lX i \i..l d i,,C i1l группы £ в слова в образующих { t ' 1,.-, ... (i& Z ),C j,j - Л , м }. Пусть , ThU) ^ T(v) принадлежат H -Hi * F , где Hi - группа с одним определяющим соотношением с кручением, F - свободная группа. В силу индуктивного предположения и С7 ] в Н можно эффектив­ но определить, пусто или нет пересечение классов смежности TfiUi)< TlVJ)> и <T(V)> . Пусть нормальные формы элементов Т (№>)» ТПО ) , Th!) в Н/V А/ -представлении группы G- имеют вид: ТШо) *•&?... i s‘ 6 ' , Vv) Ьп, где <5/ - t { , i z 1 , t ; S j / - 1 sj d i c - t t , К - i ,/ i . Слово T(W) циклически несократимо, а для T/v) , в противном случае &, 6 /i Ф -1 . Каждое B i , i <Н, в T/v) является представителем класса смежности Н ' — г по modUt■. , причем если &[ , то e>i- 6 't a , где Q- С м , если £-fl г / , и а = сД , если = - / . Аналогичным услови­ ям удовлетворяют 6 1/ , 1 s , j < S , й к , 0 ^ к < С . Цусть в (г имеет место утверждение: Зт ^/Т/УПТСИ /)* = TfV)** , г д е к,те 2 . Тогда можно эффективно определить наименьшее такое, что ш»)т(я)*^тго)лТ(кг)п. , где ш,)--тМл m U , яФШЬтМ, и между словами Т(Мо)л T(VJ)n и Т (VT) нет сокращения. Обозна­ чим символом число букв Ь и , входящих в t / . Очевидно, из выполнимости в S соотношения T(ldb)t(U/]K^ t(V )n следует су­ ществование таких Х ,у е 2 , что Т(М)л T(VJ)n TtW)x=K i r jd , кото­ рые являются решением уравнения: 128