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

то в силу индуктивного предположения в группе £■* разрешима проблема вхождения. Пусть И - произвольная конечно порожденная подгруппа из G* . Представим Н в виде SJ , где S - основа, являщаяоя древесным произведения порождающих по.дгрунп: (л/ j < № ) * . . . ш - 1 ; £ и . . к t *»i rn i . . t* * r iL t ? , ( 8 ) о<,• = О, * / ; Г у - * / , А с «У * . , J4) - множество всех нетраноформ / К.' h = . принадлежащих спе­ циальному множеству образующих подгруппы rH=ffl.(Aiof S) . Поскольку , то на основании леи,и 3 н П и ,~ (Л /4) /)С $ , где (JU,)=A4<Q£_f если среди подгрузи ряда (8) содержится подгруппа (JH1)<Qk i , в противном случае = £ . Пусть иг - произвольное слово группы . Покажем,что можно эффективно выяснить, пусто или нет пересечение игН П Ife , где H -^/l(JUo,s) • Используя алгоритм £ ? , выберем представи­ тель игс класса смежности и гН наименьшей длшш. Если Шо - 1 > то u rH ftU j- Н П Ц' =■(M ^ flU j , где Ш ,) - А , <(?^_, подгруппа рада (8 ), соответствующего подгруппе Н . Если L (u ro )~> l , то ■игНПЦ=<* . •" * Пусть LCur0) < i и иХс но содержит 1к , то есть w 0 &^x-u тогда И гН О Ц ^ш 1>СЛ'г)ЛЦ) . где СЛ/,)=А, <Q*_f , если среди под­ групп ряда (8) содержится такая, в противном случае и гН П Uj = 0 Е сли 1(ита)-Ы я ига содержит в своей записи букву , то рассуждал аналогично предыдущему, можно показать, что игНПЦ/ = 0 Таким образом, в силу индуктивного предположения в группе Q-£ разрешимы проблемы (I) - (3 ). С л е д с т в и е I . Пусть в группе Q выделена система попарно изоморфных циклических подгрупп [<Щ> ,i ^ i i i ■ Если в группе G разрешима проблема вхождения и проблема пересечения классов смежности любой конечно порожденной подгруппы Н из Я с каждой из выделенных подгрупп, то в группе раэроишма проблема вхождения. С л е д с т в и е 2. Пусть Fn - свободная группа ранга и пусть urtiVu , VJ~k , - множество слов из Fn , ш; о;шо из ко- *'/2г .