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

Лемма 1 доказана. Заметим» что если куски ^ c j , &C J непусты, то они поглоща­ ется ровно одним элементарным преобразованием (это видно из до­ казательства леммы 1 ) . Кроме т о го , слова Хс / , YtJ не могут быть пустыми для полугрупп с условием К ( г ) . Если же полугруппа удовлетворяет условию Х ( х ) & T ( s ) K слово XtJ ( YtJ ) пусто, то из леммы 1 легко сл еду ет, что в этом случае слова , *V/+/ (соответственно Yi'jn > У $*г) не могут быть пустыми. Из леммы 1 сразу вытекает СЛЕДСТВИЕ 1- Каждое слово в произвольной конечно­ определенной полугруппе с малым налеганием равно лишь конечно­ му числу различных сло в. Прежде чем доказать теорему 1 , введем понятие типа f 7 , 8 j . Пусть H i - подполугруппа полугруппы П , порожденная эле­ ментами Н - ( ; И г - подполугруппа, порожденная эле­ ментами Vt , . . . , К » . Предположим, что Н , и H i имеют не­ пустое пересечение: Р £ Н , П //,. Можно счи тать, что элемент Р записан в виде слова от образующих . Тогда Р s и ( 1 . .. u ( t = . . . для некоторых индексов Л , пу . По лемме 1 р = Ult = = л , ъ . . . п * . я , - У к , . . . * к , . . . . . а ) и выполняются все утверждения леммы 1 . Непустые слова на­ зовем Я -сегм ентами , а слова X q , К/ - сегментами. По лемме 1 Я -сегменты не затрагиваются последовательностью элементарных преобразований, соответствующей равенству ( 1 ) . Пусть Я, ~ .. . A i( . Для каждой буквы о ,у каждого Я -с е г ^ мента определим тип этой буквы. Типом буквы Я ,/ назовем ч ет­ верку чисел ( К , где - номер образующего U ls , в который входит буква P ij в равен стве ( 1 ) ; А\ - номер м еста* на котором она стоит в этом образующем; A/j - номер образую­ щего Ym , в который входит <*,j в ( 1 J ; А\ - номер м е ста , на котором P tj стоит в . Число различных типов букв конечно. Оно не превышает К , = С -т п и н *- 1 Ц П т л /х- / 1^7 . Прежде чем определить тип сегментов X / , перенумеруем все различные подслова (в том числе и пустые,) определяппих слов полугруппы. При этом подадова V/, , определяюп 1 ИХ слов W, U/j ti/( f W' U jU '} считаем различными, если U/4 ^ L ' хотя бы для одного индекса i , < & t £ i . Ясно, что общее чис­ 73