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

и V н Sc-, ,,, gr.^ . Пользуясь алгоритмом зля решения проблемы тождества в свободных сомножителях, выясним, имеет ли место равенство . Если нет, то заключаем, что С£ t V , в противном случае проверяем, выполняется ли равенство Л ‘У ~ ( 5 ~;г , и *.Д. Ясно, что дополнительное определяющее слово С £ может равняться элементу V тогда и только тогда, когда все параметры X , , Х г , . . . » X* имеют равные себе слоги в элементе V , при этом полагаем, что соот­ ветствующие известные слоги в Су и V равны. Для опреде­ ления неизвестных параметров X, , Хг , . . . , x t обратимся к соотношению " V , - . , * < * > Подставляя вмеото Ху соответствующие им слоги из элемента V и решая проблему тождества через конечное число шагов, выяс­ ним: либо а) все параметры X ,, Хг , имеют равные себе слоги в элементе I/ . Тогда заключаем, что Ct- - V в (Л ; либо б) хотя бы один параметр не имеет равного себе слога из V . Тогда Ct- Ф V в OL • ( ,у Заметим, что начало Л -7 и коней Х у . 7 не могут при­ надлежать одной и той же полугрупп. Это легко следует из усло­ вия Шопределения класса К . Лемма 2 доказана. Доказанная лемма позволяет нам строить дерево элементарных преобразований элемента W следующим образом. Пусть W = p C LQ » где СУ - выделенное дополнитель­ ное определяющее слово. Заменим С с на все равные ему элемен­ ты из дерева его элементарных преобразований с параметрами, каж­ дый из которых оканчивается дополнительным определяющим словом. Рассмотрим зацепление на границе этих дополнительных опре­ деляющих олов и элемента Q . Наличие там дополнительного оп­ ределяющего олова выясняется следующим образом. Пусть (Г/ = Л , . . . Л.р , Q = J 3 , . причем ни в СУ , ни в Q рядом нет двух слогов йэ одной и той же полугруппы. Пусть далее <v • Ляонин, вы­ полняются ли равенотва У г • “ ■ • fly .-1 - ; f i q , = С5) 96