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

{2 If In *2 )2L+2lt +Rri+e.=2m S2ltln+2mi +ctlh 2 l lh i i (Ig ) Из (18) получаем: _ S П ~ Щ / р - я ’ (19) где S - 2 iHm l , 2 W L, 2 L L^ - 2 m,U,m i - 2 m 'Wl - 2 m % < , ^ГП-Н Г% t p = < ~ 2 . Найдем множество всех пар ( n J у ) , удовлетво­ ряющих соотношению (1 9 ). С каждой парой ( п0, у а) и словом Х 0 составим набор ( л г^ Х д г п0) и проверим, будет ли этот набор решением хотя бы одного из уравнений ( 3 ' ) . В заключение рассмотрим случай 4 , когда C(w.(W) и соответственно X , входящее в набор (A2XXt n ) f валяются дельта словами. Заметам, что длина основы каждого W L не превосходит 2 т ^ 1о+2т0 (иначе получим противоречие с лем­ мой 6 ). Следовательно, .длина представления неприводимого слова X так же должна н превосходить числа 2 т™ ° + 2 г п 0 . Построим множество всех неприводимых слов X , длина представления которых не превосходит 2 т ™ ° + 2 т 0 . Возьмем произвольное слово Х«<56 и определим для него наименьшее Ро такое, что Х * =й 1 , где L четное. Для каждого i _ такого, что I ^ L й р 0 , запишем олова X 1 в виде X ^ X L, где XL е С и TL максимально возможное. Определш, оущеотвует ли среди множества слов X, слово, удовлетворя­ ющее при некотором J соотношению X j=W f . Отметим, все такие t . Для каждого отмеченного t составляем соотноше­ ния следующего вида: / № ^ Х р°(Х1=й2т4 Ц , где n=p„t +i, нир0> t*rt. Откуда ^ y ( p al « ) +Lt+2-u j . _ д 3’у ^ . Из последнего равенства получаем: (2<j.p0 * L ) t + 2 y L = 2 m i - 2 l i , ( 20 ) 1 2 y i - 2 m i - 2 i i . (21) Если система (21) не имеет решения, то уравнение (20) может иметь только конечное число наборов ( f , ■ ) , являющих­ ся его решением. Каждый из таких наборов определит решение - 80 -