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

Пусть . Ф * С т ~ ^ ijt) X , 1/ ' -t, / * / / * р * . * ЛГа, в * с £: . С? -=сГ-< • V s л £ .4 hi о(е> J где Полагая получим противоречие с условием 12 класса р ' Итак, допущение о том, что С /п, не содержится в конце С ц , неверно. Лемма I доказана. ЛЕММА 2. Пусть I /6 01а и CL 6 J , . Сущест­ вует алгоритм, позволявший узнать, равно ли дополнительное опре­ делявшее слово Сс элементу / в Qi. №и нет< ДОКАЗАТЕЛЬСТВО • Пусть множество j v ~ состоит из дополни­ тельного определяющего слова и дополнительных определяю­ щих олов, соответствующих ему в O l , т .е . •/ |'г ~ > Ci >••• С 1 Р) J • где с с- = c f e j , , / = 1>2 ....... р ' . Для каждого дополнительного определяющего слова из Л*~ рассмот­ рим его дерево элементарных преобразований с параметрами. Через А / ‘ обозначим множество дополнительных определяющих слов Q , С - ° • • • . , с } » и элементов, входящих в их деревья элементарных преобразований о параметрами. Легко доказывается замкнутость множества А / ’ относительно применения дополнитель­ ных определяющих соотношений. Из этого следует, что c - s V в 01 тогда и только тогда, когда У 6 Л / ' . В общем случае мнокеотво А /' бесконечно. Теперь покажем, как эффективно определить для произвольного элемента V из Ola, равен он CL в Ol или нет. Пуоть А / “ состоит из дополнительных определяющих слов Q . . . . СL(р> и элементов, входящих в их деревья элементарных преобразований с параметрами, содержащих не более чем д ( \ / ) больших дополнений. Допустим, _ у Ю , у ( v у У гг) U) y d ) ,(*> W с ... . ■ р. ip r С t у. 95