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

% i S i. X . Полагая ,4 2 U У£, . . • , У г У , f , В I y t-i • С I Y t l C cs > ^ l C Cs_ , . 0 y < Z > . поточим 1. 4 У ft £ v " V f , • . . V i j _ 2 V t опрелелящее 1 олово. 2. у ! . ^ C i s T Y£S C tJ J ВС - Q i - i - определяющее соотношение. 3. ХУ X Y iy -( *~cs-t ~ опРеДеляипее слово, что также противоречит уоловию Шопределения класса полугрупп К . Допущение о том, что определяющее слово содержит более одного целого дополнения,неверно. Лемма I доказана. Пусть в олове (G) У " У ^ является определяющим словом. Заменяя его на соответствующие в П определяющие слова, получим 17) U C £ 4 ; • - u 'u V , V ; > t4 У г Л и = ^ ^ * *& * ■ • Различные вонпы определяющих слов c£*J Сd- , 4 ) с различ­ ными началами слова уЦ Х ,д . . У с* Q < могут образовать новые определяющие слова. Заменяя их в 17) на соответствующие им определяющие олова и совершая аналогичные преобразования над по­ лученными словами^ получим дерево элементарных преобразований "слова . . . УскСк,- Через вонечное число шагов ^переобознаЯая различные начала опоеделяющих слов через i t j> ) в одной из ветйей этого дерева получим слово вйдв M X , V - • • , « ) где f «С,; ' с ; Уд / ■ • ■ 1 <-*Р * определяющие соотношения П , Ujj подслова, образованные из частей дополнений * . * V . - ус ^ . Справедлива следую- щая л е м м а 2 . В олове 18) <Г* К . - 107 -