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

преобразований. В множестве М ' выделим подмножество -М , состоящее из элементов вида О- И/* , где Э эле­ ментов, входящих в их деревья элементарных преобразований и удовлетворяющих следующему условию: пусть дополнительные опреде­ ляющие слова заменены на равные им в 01 элементы, длина кото­ рых с т + L • Тогда множество Q = /U ' \ J U h будет состоять из элементов вида П\ 4// и элементов, входящих в их деревья эле­ ментарных преобразований, где либо 1) выделенные дополнительные определяющие слова заменены на равные им элементы длины ^ m - t L , либо 2) д ( И Vi ) > rn L . Покажем, что в Q нет элементов длины £.Ш . Допустим противное. Пусть d(V)£. т и \ / £ Q , Случай I . оловом О- W, Элемент CL Wt с дополнительным определяющим сделаем началом дерева элементарных преобразо­ ваний. Заменяя О. на равные ему элементы из его дерева элементарных преобразований, получим а и а К\л/.Нш. W i где а * г e w . . к а. * w ? ~ i г ) . По условию случая I , оканчивается Г / = / , 2 , • •• L , 2 / дополнительным определяющим словом. Из условия П определения класса К ' оледует, что при зацеплении оно не может целиком переходить во вновь выделенное дополнительное определяющее олово Следовательно, в начале этого дерева мы будем иметь элемент по крайней мере длины m - t 1 , который не затрагивается при дальнейших преобразованиях. Значит, это дерево не содержит эле­ ментов длины & п г . Случай 2. Предположим, что в дереве элементарных преобра­ зований элемента C i w c' о дополнительным определяющим словом CLKV\/;H , rjl0 d C W ; ) > ГП L , после P применений замен и зацепления получается элемент V . В общем виде имеем элемент вида а. (-?) Гр) < < v < 100