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

В результате получаем последовательности; ОС) (Ми) W ) 4 ' t v ‘я 'г ■■ ■, 4 St'*"'» ( 04) у » у т у / » h , h , V ' » (65) ТУ" 7У" 7)" Ь 3 , ЛГ" • ( 66 ) <** • Применяем к последовательностям (5 9 )-(6 1 ) или (6 4 )-(6 6 ) соответственно преобразования о(6 , сХ? , в резуль­ тате получаем: (67) /-v. ( 68 ) # « . * 8 (69) 0 Оу* У рядов (48) и (6 7 ), (49) и ( 68 ) выделяем общие максимальные подцепочки: (M 'i,) ^ (M i2 ) * . . (70) /—W X ~ Х> ^ 6 ^ (7 D ° 0 б7. Пусть ( 7 0 ), (71) - р езультат преобразований Л ,,,, И пусть для рядов (7 0 ), ( 4 8 " ) , (48) справедливы равенства: ( Ц и к Ш Л - --, № ф (м ^ , ) - (& , ) и для рядов ( 7 1 ), (51) L ,-L . Пусть также Х'~Х , ^ ' . “ Х и < ^ И М ^ ) - и ^ ( К , ) и г , Ш ( М ^ , М ‘ И % , ) . Тогда рассматриваем ряда: ( # , ) * . . . ^ (72) { V , р»/ X ^ _ X, (7з> Можно убедиться, что подгруппы ^ 11 слова М}10~ жества C = f X /,Y '......Y ' } обладают свойствами а , - а^- и , следовательно, порождают подгруппу g p ( J u - , i > ) , где о подгруппа, порожденная подгруппами ряда (7 2 ). - 59 -