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

B („ W = h , (20) где W e A sj , , если • и h ^ U -t , если &LH=l Если соотношение (20) выполнено, то длину w ' можно укоротить. 2 . Допустим, что либо соотношение (20) не выполняется. Выделяем в подмножестве A f c x . г t<& , если это возможно, нетрансфюрмн вида: где ft - О, ±- f , Затем проверяем справедливость соотношения: В ыW = / l K w либо B L w = h r ,L+f> W c /L - , h е Ц , если = , и h € Uit ( 20 ' ) ( 20 ") если где »v~ -i5 . $.+,= < . Справедливость соотношений (2 0 ), ( 2 0 ') , (20") проверяет­ ся эффективно, так как по условию теоремы I в группе G раз­ решима проблема пересечения классов смежности конечно порож­ денной подгруппы из G с подгруппой Ц и (Z , . 3 . Допустим, что соотношения (20) и (20") не выполняют­ ся. Тогда проверяем справедливость соотношения: &U< , (21) где к ^ Ц , если S[H = - / , и k*U 4 t ecote t LM = t , W e /l y , $>iH - с л о гаю в а t JA 'I, , нумерующего множест­ во tP , если вершина, соответству­ ющая множеству 4 (^2 ^ [е,х,1р , не является конечной верши­ ной граф Гш . Слег &iH переводится, если это возможно, только в один ив слогив а слова г, t p , так как иначе получим противоречие с ( а * ) . Если £ U t ^£c+t , то применяем O t, , в противном слу­ чае переходим к O lg . Otg. Пу^ть множество A t(n ( & r,t* не содержит под­ группу (M ij-J-t - 38 -