ВОПРОСЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1972 г.

■\ А.Е.УСТЯН О СВЯЗИ МВДУ ПРОБЛЕМОЙ ВХОЖДЕНИЯ И ПРОБЛЕМОЙ ТОЖДЕСТВА В ПОЛУГРУППАХ Известно,что из разрешимости проблемы вхождения следуй разрешимость проблемы тождества в группах, В настоящей ваметке рассматривается аналогичная связь в полугрупп»*, Пусть полугруппа П задана образующими «Ц,---- д и рекурсивно перечислимым множеством определяющих соотщ пений и пусть в »той полугруппе разрешима проблема вхожд» ния. Имеет место следующая Т е о р е м а . Из р а з р е ш и м о с т и п р о б ] мы в х о ж д е н и я в П с л е д у е т р р е ш и м о с т ь п р о б л е м ы т о ж д е с т п в П . Д о к а э а т е л ь с т в о . Пусть X и у — слова пш группы П • Выясним при помощи имеющегося в нашем pecnopi жении алгоритма,принадлежит ли слово X подполугруппе,* рожденной словом ^ , и принадлежит ли слово £ под* лугруппе,порожденной словом СС . Если X не принадлежи или £ не принд лежит подполугруппе, порожденной X ,то заключаем,что Пусть Л: принадлежит подполугруппе,порожденной сломи и и принадлежит подполугруппе,порожденной словом X > ' л У * ^ ( 1 Совершая в некотором порядке преобразования в словах 1 * £ 7 через конечное число шагов мы найден oi. и f ' подполугруппе,порожденной словом ljf