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

где "/£^ s ■&р - 1 , f s 9 - & ^ . Если все равенства (5) выполнены, то с содержится на границе Сс и Q , в противном случае - нет. Ясно, что число дополнительных опреде­ ляющих слов, если они имеются на границе CV и Q , ограниченно, Пусть все равенства в (5 ) выполнены. В силу свойств свободных сомножителей найдем все элементы У, таких, что =у'г У 1 . Это требование существенно, т .к . следующий шаг в преобразовании элемента W состоит в замене всех вновь выделенных дополни­ тельных определяющих слов на разные им в ОС элементы из их деревьев элементарных преобразований. Все они оканчиваются до­ полнительными определяющими словами. Не исключена возможность, что на Границе этих дополнительных определяющих слов и элемен­ тов У 1 имеются дополнительные определяющие слова. Для того чтобы эффективно их выделить, мы должны знать вое такие парамет­ ры У , . В дальнейшем мы не будем выделять эти параметры. Будем рассматривать зацепление, считая, что параметры нам известны, поскольку умеем их находить. Таким образом, для получения дерева элементарных преобразований W с выделенным дополнительным оп­ ределяющим словом достаточно повторять всякий р а з‘следующие опе­ рации. а) Заменить вое выделенные дополнительные определяющие оло­ ва на вое равные им элементы. б) Рассмотреть зацепление. После конечного числа применения операций а) и б) в одной из ветвей дерева появится элемент вида с и < 4 ' ! 4 , с - и х £ c Lt „ Q * . . , где ~ **ч 2 ' , оо а ) J /г) , ( , i p (& ,) ^ср„ Xj I p,i, Xt1 ( 6 ) _ / s » / W v o * i") • " «"Cl ••• ^ l P .X v -V ^J41 . CU s > / Легко доказывается, что если дополнительное определяющее слово оодержится в н О) ы x c , t , Xt , V f < '! у / , то только в конце С ,т . t L 1 / 97