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

то I. Если /} =B e J 1L А - - С € З г А*С . П. Если Z ^ Z , и В - С G J j , тогда и только тогда, когда J j z 0 e j , то Z - пусто. Ш. Невозможно одновременное выполнение условий I) A x B e J , . 2) В С =У£>€ J± . 3) Х У е , где В , X , У непустые. 1У. Сг - конечно. У. Если CL £ J, , то д С С с ) > 1 . Нелью настоящей заметки является доказательство следующей теоремы. ТЕОРЬМ . Существует алгоритм, позволяющий узнать для любых двух элементов vV и V' из (Ла равны они или нет в C l - O i 0 / J z e B ' . Для доказательства теоремы нам нужны некоторые дополнитель­ ные сведения и леммы. Пусть CL G J f • Ясно, что C't имеет лишь конечное число дополнительных определяющих слов, соответствующих ему в (Л j О) ЧТО С; СЛОВ с° - Г<Р> CL = где ( р ) с . -- с ' e j . Q j = 1, ~ р ) . Согласно условию П К ’ , осли дополнительное определяющее сло- определения о а с о а во c '/f ) содержит другие дополнительные определяющие слова то только в конце. Как алгоритмически выяснить это? Пусть г ы ? ■ 4» - а <^сг ••■’{су, • " V C / ' f / 2 ч/ s ' Согласно свойствам свободных сомножителей, мы имеем возможность проверить выполнимость следующих равенств: Ф а 9 Ф Ф J s e J > - а У(г> - Г 9" ~ j /s ' ^ l ?- i - f t z s - 1 > " ' 9 г — * Ф ( 2 ) / й . г < X - неизвестный пока нам параметр, воэ- где можно пустой. Если в (2 ) выполнены вое равенства, то заключаем, что Cf содержится в конце с Ф ,в противном случае оно не содержится там. Таким образом, мы умеем ответить на вопрос, содержится ли одно дополнительное определяющее слово в конце другого. Найдем все дополнительные определяющие слова, которые 93