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

Из построения вспомогательного ряда следует, что ^(М) В результате применения преобразований ^ суммарная слоговая длина преобразованного вспомогательного ряда подгрупп (Д ') не во зр астает, то есть l~jy . И суммарные слого­ вые длины рядов, полученных из (45") и (46") применением oLj-QL/f, удовлетворяют соотношениям: Очевидно, преобразовашш - а(? можно применять только нонечное число раз. Преобразования о , , , - , не меняя длины , А-0 , преобразуют начальные и конечные подслова одинаковой длины рядов ( 4 5 " ) - (4 7 * ). Но так как число различных начальных под­ слов левых крыльев подгрупп ряда (45") и число различных на­ чальных подслов левых половин слов Y * , & - t l , ряда (46") конечно и применение преобразований d 1tl - на каждом шаге уменьшает их чясл , то через конечное число шагов ряда (45") - (47") преобразуются в ряды, инвариантные относительно этих преобразований. Пусть <W), W y) - подгруппа группы С * , поровден- иая множеством слов W, , , . . . , W # . Упорядочиваем это множество по длинам: W, Рассмотрим подгруппу, порожденную одним словом \У/ . Очевидно, множество fW j яаляетоя специальным, а поэтому подгруппу (W ,) можно представить в виде подгруппы фр(М0>$ ) , то есть через порождающие подгруппы, удовлетворяющие условиям а , - а3-: < % ) * » № , V й). Затем к подгруппе , урШ 1‘\ S C1)) ) применяем преобразо­ вания aL 0 - , переводящие через конечное чиоло шагов под­ группу S{,>) ) в подгруппу и т *д * В результате черев конечное чиоло шагов подгруппу преобразуем в подгруппу yp (A l0,S>\ ТЕОРЕМА 5. Сущестдует алгоритм, позволяющие любое конеч­ ное множество слов группы <г* преобразовать в множество, удовлетворяющее условиям ( i ) - ( i v ) - ^ Пусть имеется конечное множество слов {иъЬгрР группы С , - 61 -