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

Бели среди слов дереве элементарных преобразований 113) ебть Та­ лое, воторое своим началом имеет W , то его яонеп и является исвомым словом X , следовательно, уравнение Д/ — U / X разре­ шимо. 1 Воли не нет тавого слова, то преобразования над словами дере ва (13) продолжаем дальше. Согласно лемме 1, если на границе слов , ц и У к *1К1 ( , и v «» *ai Ла* ' « и » " ДД *1 к «1 * и - Y U ' * } K J , где 1 = 1) Л, . • . ^ , имеются определяющие слова, то они содеряат на более одного це­ лого дополнения. Согласно лемме 2 после замены всех выделенных определяющих слов на соответствующие имоопределявшйе слоба, мы получим стольво не дополнений. Согласно лемме 3 преобразования происходят тольво вправо от выделенного определяющего слова. Тавим образом, заменяя вое выделенные определяющие слова на равные им олова в Г | \ содериащие не более чем £ ( И') -+ L дополнений, через венечное число шагов в одной из ветвей дерева элементарных преобразований (13) в общем б^учае поЛуДим слово вида: . . . ' .. V X V - - U ' h X - V I W W K f " и , „ У l И l^ .+/ l - - • I у ) могут быть пустыми. Взли есть слово вида (14 ), которое в начале содержит олово Г Н- то зовлючаем.что исвомое слово X найдено и уравнение I / - Н / у. разрешимо, в противном случае нет тавого олова X чтобы 1 /= И / X в П . Теорема довазана. О Л и т е р а т у р а I. I . А д я н С. И. Определяющие соотношения и алгорйтмйЧесвие пр блемы для групп и полугрупп .-Труда маТем.института им.В.А. Стевлова, 85, 1У66. - 112 -