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

перестановкой а сопряжением элементом из объединяемом подгруппы ЛЕММА Щ З ] . Существует алгоритм, позволяющим для любых двух конечно порожденных подгрупп Н, , нх свободной группы F выписать образующие их пересечения. ■Ш.М i a f n j. Существует алгоритм, позволяющий для любых двух конечно порожденных подгрупп Ht , Нх свободной группы F и любого элемента w e F установить, пусто или нет п ересече­ ние wH 1 о Hi , и если нет - найти элемент из ЛЕММА 1 3 [ 5 J . Пусть б - некоторая группа, w , и , гг - элементы из В бесконечная циклическая подгруппа В. Если ( I * - множество натуральных чи сел, вклю­ чая 0 ) и и 1* м 1 , то u * F w * Рассмотрим группу ф * < а ,о х ..... ап , bfi А , ......4 » ; V , = Г ( Ц > * (84) являющуюся свободным произведением свободны:; групп Fn' <o ,i ..:,a n >, Ртл< 6 - г , bm > I объединенных по изоморфнымподгруппам Ц < Рп> U 1 <Fm iT R eU ^ < a , ^ j . ...в Д Щ ,... ,<*„)>, *< *, f,( a „ ...,a nj 4 < a 0 ...,a k > и $ , К < Ь , h ( b , ...... b „ ) 4 < b „ ...b k >, h < m . И t i* % k , Si 4 О и P i 4 0 , у _ фиксированный изоморфизм У, на ££* , Таким образом, G, можно записать так й г< о , Qn,ь,,. ., b m ; f Kqf t f , f o . ( 85) ЛЕММА 1 4 . Пусть Н - конечно порожденная подгруппа свобод­ ной группы F и и / - произвольный элемент из F . Тогда мож­ но эффективно установить, существует ли i e F та к о е , что ДОКАЗАТЕЛЬСТВО. Пусть w - циклически несократимое слово и - нильсеновское множество образующих подгруппы Н. Обозначим через a*>niu(lu,l,...l iUf>l). Выберем X наименьшим в двойном классе смежности , можно убедиться в том, что fif&Lh/Ve, СЬставим конечный список слов , где /2;) * 4J0 , ж для каждого Ж( определи^, входит ли элемент г 1\н 1 1 в Н , £ * ± I . Проверка этого условия проводится эффективно, так как в F разрешима проблема вхождения. Лекма доказана. 29