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

^ г - ^ 4 * 1 ' " Гяе Т X<,j ^ i j * | f j ± / • Таким образом, если определяющее олово Ct со­ держится в слове У ,, X13L' • • ■ y,s d , f| . то оно содержится» в вонпе 'S i . Различные вонпы определяющего олова 3 ) о различными нача­ лами слова If" могут образовать определяющие слова, очевидно, что Их вонечйое число. Заменяя их На соответствующие им В П определяющие слова, получим ■ ’ j X.,-- ■ * „ с „ # № и ' Г W • • Xi k , •■ (Ш .1 1U , ■ В Ш ) определяющие слова могут быть на граниле определяющих слов и U " U L , i- z 1,3.0 ■> & р Заменяем их на соответ­ ствующие им.в П определяющие слова И т .д . По допущению сущест­ вует последовательность U 0 ), переводящая слово • )(,fC1sV в слово V N . В общем виде это слово 1f* может быть Представле­ но следующим образом: *•. • ••. c l , э , Ч ч . • . О Д % (У * ц Где tf< - вояеп Слова, V - возможно пустой, 0,н, . • .,2£ - различные начала соответствующих определяющих слов, Что пойаай­ ва ет незатрагиваемооть дополнений *Vi, Xj»,, t fy . Лемма 3 доказана. Теперь докажем основную т е о р е м у . С помощью алгоритма, решающего проблему тождества олоВ в По­ лугруппах из нЛасоа к , выясним,равно ли оЛовй V слову № в П или нет. Бели V - W в П , то На основании теоремы, доказанной в [б ] (в полугруппе П не существует последователь­ ности элементарных преобразований, переводящей слово X в слою У-2- ), заключаем, что в полузд>уппе П нет непустого слова X такого, чтобы V - 1^Х • Допуотим, что [/ -ф W в Г] и пусть где ^ i Ц с, ... с,., Ч -,С^, ( 12,1 [ / ; - могут быть пустыми, р . - выделенные определяющие ь '-'l - НО -