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

2 . U = Х(-4 . . . Х (к , V = Y,t ... Y ik , причем для слов Yij выполняются утверждения 2 , 4 , 5 леммы 1 (с той разницей, что в 4 ,5 индекс / изменяется от 1 до К , Л / * ,, совпадает с A , С * . * совпадает с Cl f ) . ДОКАЗАТЕЛЬСТВО лешы S аналогично доказа­ тельству леммы 1 и поэтому зд есь не приводится. СЛЕДСТВИЕ 2 . Каждое слово в произвольной конеч­ но-определенной полугруппе с малым налеганием сопряжено в пер­ вом роде конечному числу различных сло в. Отсюда очевидным образом выводится теорема 3 . В заключение докажем одно простое следствие из статьи М.М.Лесохина [ 1 2 ] . При этом будем опираться на некоторые ре­ зультаты из [ 1 3 , с . 1 2 8 -1 3 0 ]. ОПРЕДЕЛЕНИЕ 5 [ 1 4 ] . Подугрутгавов непредстав­ ление П - < ЛА } = 6 ; , i ' e i > называется F Е С -копредставлением, если с помощью определяющих соо т­ ношений А\ - в,- любое слово в алфавите # = [ * / , •■•> а л ] можно перевести лишь в конечное число различных олов ( г . в . соответствующая конгруэнция разбивает свободную полугруппу U * на конечные классы эквивалентности]. Полугруппа $ , изоморфная некоторой полугруппе П , заданной F E С -к о ­ представлением, называется F E С -полугруппой. Сразу из определения следует, что F E С -полугруппа не может содержать нулевого элемента. Далее мы будем рассма­ тривать только конечно-порожденные F E С -полугруппы, не содержащие единицы. Следующие две леммы очевидны, ЛЕММА V. Пусть 5 - произвольная F E С -полу­ группа, не содержащая единицы. Тогда множество U. - S \S* неразложимых элементов полугруппы S непусто и любой эле­ мент из S р азлагается в произведение элементов из # . ЛЕММА 8 . Полугруппа S , не содержащая единицы, является F E С -полугруппой то гда и только то гд а, когда любой элемент т е f имеет лишь конечное число различных разложений в произведение элементов из t C - S \ S . Следующую лемму интересно сравнить с предложением 1 .5 [1 3 , с . 1 2 9 ] г- оказывается, что кл асс конечно-порожденных свободных полугрупп совпадает с классом конечно-порожденных равноделкшх . F E E -полугрупп. ЛЕММА 9 . Кон'ечно-псрожденная полугруппа S , нс