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

ло различных подслов конечно. Обозначим это число через М , Можно найти верхнюю оценку для М , но мы этого делать не су­ дей . Типом сегмента назовем шестерку чисел (N& Ц , Л/?, vtj N 3 , ^ 10 ) , где N s - номер образующего , в который входит последняя буква слова Х у Сем. второе графическое ра­ вен ство в ( D J I А /( - номер м еста, на котором э т а буква ото- ит в t l у ! N y ‘ - номер Х у в множестве подолов опреде­ ляющих сл о в. Если при этом сегмент Х у окажется пустым, то AV и А/( определяются по последней букве сегмента Числа N f , N) t Nta определяются аналогично по сегменту У у ( т .е . N » ,N s соответствуют вхождению последней буквы слова Уу в образующий - см. третье графическое равенство в ( 1 J ) . Число различных типов сегментов конечно и не превышает числа К • К , - М г . Обозначим через С максимальную длину определяющих слов полу­ группы* ЛЕММА ' 2 . Если конечно-порожденные подполугруппы И , и H t полугруппы П g малым налеганием имеют непустое пере­ сечени е, то существует элемент Р е Н ,п Н л такой, что его можно запи сать в виде слова от образующих полу г руппы П длины не бо л ее, чем Kt + K j j С . ДОКАЗАТЕЛЬСТВО. Так кех Н ,П Н Л * 0 t то существует минимальный (по длине в образующих полугруппы Н ) элемент Р из пересечения И , и H i . записанный в Виде произведения образующих подполугруппы Н, , Допустим, что IPI > К, t * 1 - с . По предположению леммы, выполняется равенство ( 1 j , Обоз­ начим суммарную длину всех Й -сегм ентов из (1 ) червя L , , а количество сегментов Х у через L>t . Так как Х у - под­ слова определяющих слов, то общая длина всех Х у не более, чем L t С . Тогд? должно выполняться хотя бы одно из следу­ ющих условий: 1 . L 4 > К , ; 2 . L t > кг . Пусть имеет место случай 1 . Тогда общее число букв в R - с е г ­ ментах превышает число различных типов букв, поэтому в £ - сегмен тах найдутся хотя бы две различные буквы, имеющие одина­ ковый тип. Пусть это будут буквы о ' из сегмента И - и а "