АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

Т е о р е м а 2 . Если для конечно-определенной полу­ группы Сг , принадлежащей классу , существует алгоритм для решения проблемы тождества сл ов , то существует алго - ритм для решения стр ого ограниченной проблеш изоморфизма для полугруппы Сг , О п и с а н и е а л г о р и т м а . I . Устраняем все определяющие соотношения вида С =0 из полугруппы Ф у , по­ лучая изоморфную ей полугруппу Ф, . 2 . Если Сч„ =С'<г и Ct2=C-i .3 - определяющие с о о тн о тз- ния в полугруппе ^ , но С *Л£ , , то добавляем к опреде­ ляющим соотношениям полугруппы определяющее соотношз- ние С-Ц = С < з , повторяя этот процесс до тех пор, пока это возможно. Получим полугруппу 3 &2 » изоморфную полу­ группе С &~| ._ 3 . Для каждого взаимно однозначного отображения об­ разующих элементов полугруппы на образующие элементы полугруппы С г проверяем, пользуясь алгоритмом для реше­ ния проблемы тождества слов в (л г а ) переводит ли все определяющие соотношения из <$г в равенства из & и _ б ) переводит ли '/"* все определяющие соотношения из Сх в определяющие соотношения из ^ . 4 . Заключаем, что полугруппы От и изоморфны ( с о ­ ответственно, не изоморфны,), если существует (с о о т в е т с т в е н ­ н о, не сущ ествует) отображение Ч , удовлетворяющее выше­ описанным свойствам: За и 36. Д о к а з а т е л ь с т в о . Тот факт, что существо­ вание такого отображения 'f влечет изоморфизм полугрупп Q и , очевиден. Допустим, что полугруппы О и ф " изоморфны квжду с о ­ бой. Тогда по лемме любой изоморфизм f полугруппы на полугруппу Gr взаимнооднозначно -отображает образующие эле­ менты полугруппы <#г на образующие элементы полугруппы G- . причем f'XM ) и f являются определяющими словами полугруппы фъ . Если, кроме т о г о , множество f o - Dj является множеством определяющих с о о т ­ ношений полугруппы Фр, то все слова Cj и 1>0 не пусты, х если некоторое или DkC^k^S) не содержит ни одного - 8 -