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

торнх не равно пустому слову в ^ . Тогда в группе (r*=-< Fn, t/u r , *чя Ц , =Z£ > разрешима проблема вхождения. Действительно, в группе Fn разрешима проблема вхождения, и в [4] показано, что в Fa разрешима проблема пересечения клас­ сов сменности конечно порожденной подгруппы с циклической под - грушкй. { Л е. м ы а 4. Пус^гь - НМЛ' - расишрение свободного произведения (г» П *&s групп <rs , s*jTii , с помощью конечного набора п ар ,изоморфных подгрупп Щ Щ У & с , Uji- . и фиксированного набора изоморфизмов Л , - U jt . Тогда, если подгруп­ пы Uij обладают.свойством максимальности в каждой группе Gs , s = .. разрешимы: (I) проблема вховдешм, (2) проблема пере­ сечения классов смежности любой конечно порожденной подгруппы Н < (?5 с каждой из подгрупп Vsj < 6?s , (3) существует алгоритм, выписывающий образующие пересечения любой конечно порожденной подгруппы H<QS с каждой из й,- *(?s , то в группе Q * раз­ решима проблема вхождения; { £ty J - система правильных проход­ ных букв. Д о к а з а т е л ь с т в е Для доказательства необходимо убедиться, что в группе П* <?s разрешима проблемы (I) - (3 ). Разрешимость проблемы вхождения следует из [5]. Покажем разре­ шимость проблемы (2) и (3 ). Проведем доказательство для случая, когда ( ? , и для определенности положим i-< : ■*<}■, . В работе [6 ] введено понятие нильсеновсного шожества слов в сво­ бодном произведении груши О п р е д е л е н и е 3 (6 ). Множество слов W - l i u ip v группы 0 = ^ *6гг называется нильоеновсним:_ £ а) если L (и /* '.. где £ < - * / , £= /, п ., }\ в слове ,’urf* нельзя выделить подслова urf/. w f* , / а / * s e n , равное I в образующих ьи, в группе Q ; б) лова?? половина слова w t- W , но являющегося трансфор- мой, изолирована n Кк ; в) если иги - уя _ слово нечетной слоговой .длины, то но существует слова иге<цг( Н/\игл ) такого, что и ^ г у - 2 £ Кл v ’J ; г ) осли имеем дво транофорш 1 ^ г г л Кы ь - ^ > ,