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

к * 2 t L M l C l + t L + C + L + e lL l M lc + l l L l + I C ( C + L ) } где t - число порождающих элементов H , L макси­ мальная длина слов , С - максимальная длина опреде­ ляющих слов полугруппы, М - число различных подслов опре­ деляющих СЛОВ ПОЛУ'х’РУППЫ. Пусть выполняется ( l l j , ^ U j(% причем S - мини­ мальное из всех возможных. Сразу заметим, что из минимальности S следует U i 4 . . . з U j Допустим, что сум­ марная длина ( в образующих полугруппы П ) обеих частей соот­ ношения ( ' l l ) минимальна в множестве все х нетривиальных соотно­ шений. Покажем, что в этом случае левая и правая части ( 1 1 ) имеют длину не более К . Пусть / Щ 4 .... U t l \ > x . Тогда должно выполняться хо тя бы одно из соотношений: ii / U 4 u . . . K i J > t l L l M ' C + 1 1£*г + £ с ( C+ L ) ; 2. > x t ^ H l C l * t L + С . Рассмотрим эти случаи отдельно, заметив, что по лемме 1 равен- сТво (11) можно записать через сеш ентн пусть выполняется случай 1 и пусть P i , X cj, Y ij . Итак, U : . . . 1 L : 2 - где \Р] - Х С ( с + L 1 . Тогда . . . K - t l > * e l L 2 и теперь, как и в лемме 2 , с помощью метода типов можно умень­ шить длину соотношения ( 1 1 ) , определив типы сегментов в слове #,• ■. . и выбросив некоторое подслово из обеих частей (1 1 ), Причем в правой части выбрасывается некоторое подслово слова --- ty f, . т . е . слово & /t при этом не затр аги вает­ ся - это следует из минимальности числа S , леммы 4 и опре­ деления длины слова Р . Таким образом, мы получим нетриви­ альное соотношение, длина которого меньше, чем у (1 1 ), что не­ возможно. Значит, случай 1 не может выполняться. Рассмотрим случай 2 . Можно применить лемму 4 к ( l l ) , где роль слова £ играет Щ \ -, , Е = Е ЛЕ-, а Е п - конец слова Е длины С . 2 .1 . Пусть суммарная длина Р -сегм ен то в в слове £ л больше t L . Тогда мы можем уменьшить длину равен ства (1 1 ),• выбро- e i