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

L ( uq ) Ugi*V$ , К* > принадлежат одному сомножителю группы Gr , то не существует слова ttreg/i(w ) такого, что и Г '^ /С , Ш')иг= щ Л> v / f Понятие трансформы и нетрансформы группы <?«<?, *<?а данЫэВ [8] . В работе |,6'j доказана т е о р е м а 4. Если в сомножителях Qc , i=1,2 , груп­ пы разрешима проблем вхождения, то существует алго­ ритм, преобразующий любое конечное множество слов в С? в нильсе- новское. Поэтому в дальнейшем будем считать, что образующие подгруппы H<G приведены к нильсеновским образующим = , с которыми связано разложение подгруппы Н э свободное произ­ ведение: 2 , (9) где F - свободная подгруппа, порожденная всеми нетрансформами из W , a Gv t - подгруппы, порожденные трансфорыаш V Л/ Vi 1, где K^Gr-f аналогично Grv' £ порокдебы трансформами Vj'Kj где К '- * а г . / " • . / " • Из свойства (а) нильсеновского шожества следует: HOU ,j-(хц^АЦ ], где G-ц. t , если такая подгруппа содержится в разложении подгруппы Н , в противном случае Н П и ^ = Е . Отсюда следует разрешимость проблема (2) в группе G Пусть w g G- , покажем, что можно эффективно выяснить, пус­ то или нет множество _ w H Г) Ufj . Для этого выберем в классе ■ смежности w H в качестве представителя элемент наименьшей дли­ ны. Алгоритм выбора такого представителя состоит в следующем. С каждым конечным подсловом u s " слова и г = и/'ит " ,Л(иг)=1(иг')+Л(иР'), 0< L (w ") -&/L(ur) , свяжем множество Vw „ конечных подслов w fn , < где uri e w > 0 i G(iufn )<[G&L)] L(wfn )* -L (w ") ,L (w ^w fn )*L( w )< ( uj Q . Образуем сл о в а us"4 uJ}„, для ко­ торых решаем принадлежит ли us'~'urfn подгруппе М • Выбираем из слов U fS 'w ^ е / / такое, у которого l(u jfn ) имеет наименьшую слого­ вую длину и заменяем и г словом u s(u f^u sfn ) . Процесс начинаем с множества Vyj. . Если для нсг$ не существует слова w~4<rfn удовлетворяющего высказанным .требованиям, то переходим к Уа^..,о.т> где О,. Qm - каноническая форма и г , и так далее. Нетрудно показать, что первое полученное в указанном процессе слово UfUSn u£, и будет ш0 . 1 4 -