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

Заменяем ряд (45*) рядом (6 7 ), ряд (46*) - рядом ( 68 ) , ряд (47 ) - рядом ( 6 9 ), ряд (48) - рядом (7 3 ), ряд (49) - рядом (7 3 ). °Чб .з • Пусть (70) и (71) - результат преобразований QLaa , , °W и пусть , д я рядов (7 0 ), (48'*), (48) имеют место равенства а для рядов ( 7 1 ), (49) L, = L а X =X j - . , X . , ~ Y i . Пусть также Тогда рассматриваем ряды: ( ( 74) г' /Л (75) Можно убедиться, что подгруппы ряда (74) и слова ряда (75) обладают с в о й с т в ам и ^ , - а*- и , следовательно, порождают подгруппу ЯР( £ ; > ? ) . где Г - йод- грудпа, порожденная подгруппами ряда (7 4 ). Заменяем ряд (45*) ■рядом (6 7 ), ряд ( 46") - рядом (68) , ряд (47") - рядом (6 9 ), ряд (48) - рядом (7 4 ), ряд (49) - рядом (7 5 ). Допустим, что ни с , ни ct,b i нельзя осущест­ вить. Тогда заменяем ряд ( 4 5 ') рядом ( 6 7 ), ряд (46") - рядом ( 68 ) , ряд (47*) - рядом (6 9 ), ряд (48) - рядом (7 0 ), ряд (4 9 )- рядом (7 1 ). Выполняем преобразование . ЗАЖЧАНИЕ. Если подцепочки (5 6 ), (5 7 ), полученные пре­ образованием пСв , либо (7.0) и (7 1 ), полученные преобраэова- кием oilf , тлеют нулевую длину, то есть ( 3 = ^ “ ^ , то в качестве подгруппы g p (4 > ',S ') ш берем либо подгруппу (М{,) если 2Ш а (А1 ц ))+1 * к Р у ,) , либо циклическую подгруппу (S t,'У > в противном случае. Покажем сходимость построенного алгоритма. Сумму Аа= X, (21 (Кл(Ъ;)) +/) будем называть суммарной слоговой д иной ряда (47*), сумму =£ («л(М^)У/ ) - суммар­ ной слоговой длиной ряда ( 4 5 ') , a L0= Z l(Y 'j - суммарной слоговЙ: длиной ряда ( 4 6 ') . ° t=/ ‘ - 60 -