АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

Тройну (Нр, Кр ,Zp) обозначим через Рр . При соглалкнии Н ы ^М о - К 0— обозначим через L , L,0-, соответственно слова А или Б , И0 или 1^о »• •• Сформулируем свой ство, которое непосредственно вытека­ ет из условий С /1 /4 / и Т. Л е м м а 9 . Пусть Т - сегмент L и является частью некоторого определяющего слова. Пусть Рр будет К -п ри ве­ дение. Если T n L p ^ I , то справедливо утверждение 1 . Z p "^ I влечет T n L jp ^ I и ^ I влечет ТО Ьр -4 ^ I . 2. Если Z p ^ I и TnL.p+ 1^1 и, к тому же, Р рм есть свободное приведение, то T n L p ^ I / ^ R . Если Z p -t'3,I , T n Ьрм Ф I и PpJ - свободное приведение, то Т п Ь р ^ ^ 1 /4 Г ‘ Основываясь на приведении АВ к одному из ввдов ( i ) - ( 4 ) , докажем еще две леммы. Л е м м а 10. Если А и Ъ -неприводимце сл ова, то в результате применения к слову АЬ свободны* приведений и R -приведений может быть получено R -приведенное слово AkSbm , где Ак- начало А , В т - конец Ь , |S|< и г* - максимальная длина определяющих сл ов, участвующих в преобразованиях слова АЬ. Д о к а з а т е л ь с т в о . При переходе от ( I ) к ( 2 ) при помощи m R -приведений из слова С2Ь> получи­ ли слово М/|Н2 . . . UmE>m • При каждом ft-приведении длина слова, к которому применяется R -приведение, умень­ шается, по крайней мэре, на единицу. т 1 2 | 0 а|, так как в противном случае, в силу В = СГзСгЪ = C gR i . . .HmBm н IC 2 H 1 Н2 •••Нгп^Вгп I 2 1 C 2 I+ 1Ы - гп , имеем противоречив с неприводимостью слова Ъ . В свою очередь, Сг 1 /4 R , поэтому m<i г*/ 2 , а, так как IИч 1<.r»/2 , то Щ ,..Н от]< г74. Аналогично получаем ограничение на К и (Ek. . . . E i | .От­ куда ограничение на S с запасом: IS K г г. - 27 -