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

УДК 519.4 А. Е. УСТЯН Тульский пединститут ПРОЕДЕНА ТОНДЕСГВА СЛОВ ДЛЯ ®АКТОР-ПОЛУГРУПП СВОБОДНЫХ ПРОИЗВЕДЕНИЯ Пусть полугруппы D l , , ( X , , . . . . O L^ , заданные соот­ ветственно множествами образующих Rt , Г& , . . . , и опре­ деляющих соотношений R f , R 2 , R ^ , имеют разрешимую проблему тождества слов и разрешимую проблему делимости. Кроме того, если а и б принадлежат O t± (<■-/, — / 2 ) , т о суще­ ствует лишь конечное число элементов x e O t ^ таких, что q = 6 jc } и существует алгоритм их нахождения. Как извеотно, полугруппа O l 0 = O t , * O l a * o t b , представляющая собой свободное произведение полугрупп Ot 7 , за­ дается образующими Г - О и определяющими соотношениями R - 0 R t . Полугруппы Utf , . . . , O tл будем называть свободными сомножителями. Через O L=O t 0 / J 3 обозначим фактор- полугруппу свободного произведения по множеству J s , где J 2 - множество дополнительных определяющих соотношений вида . . . аСр * />гJ $3 ■■■ . Cl) Здесь <^i и J S - , которые мы будем называть слогами, являются элементами Otr , . . . , 0 7 а , причем пары чСл и X ^ и С ? л Л * р - / , / л ) принадлежат различным полугруппам. Как левую, так и правую часть ( I ) будем называть дополнительным определяющим словом. Через Е7, будем обозначать множество дополнительных определяющих слов, а через ДЛ = JUO t^ . Будем различать равенство в полугруппе О Н - ) и равенство в полугруппе О 10 С='> . Пусть И / = ... -элемент из O ia , где /72 2 / . Длина элемента и / равна л ь и обоз­ начается через d ( w ) , Нели Е t - Fc е О, , то под L будем понимать д ( т а х ( { £ , } , { р ]) ) Будем говорить, что фактор-полугруппа O l ~ O t 0 / J 2 при­ надлежит классу К ' если выполнены следующие требования. 92