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

V f полугруппы '<& на полугруппу Gr , определенное равен­ ством V 'f f c i j) = у ^ ( с ^ ) ) , является изоморфизмом ^ на 6 г . Т .к . y C t fa j)) =<5j; Q = I , . . . , n ) , тоЧЧ отображает слово С] на Cj и слово на слово D j . Следовательно, в по­ лугруппе f t имеют место равенства C j s D jQ f c A ) . Этим за­ вершается доказательства теоремы I . Под стр ого ограниченной проблемой изоморфизма для к .- 0 . полугруппы & , заданной образующими эле мантами d ,,...,6 > n и определяющими соотношениями A i = B i ( i = 1 , . . . , к ) ш бу­ дем понимать следующую проблещу. Найти алгоритм, позволяю­ щий для любой полугруппы 'J y, заданной теми же образующими элементами £ ц , . . . , 6 п и конечным числом определяющих с о ­ отношением, узнать, изоморфна ли полугруппа £&’ полугруппе ( х , или доказать, что такого алгоритма не существует. Строго ограниченная проблема изоморфизма для любой К .- о . полугруппы ft из и проблема тождества слов для этой полугруппы эквивалентны между собой , как будет ясно из следствия I теоремы I и теор еш 2, N С л е д с т в и е I . Если для конечно-определенной полугруппы 6* , принадлежащей классу К / , существует алго­ ритм для решения стр ого ограниченной проблемы изоморфизма, то существует алгоритм для решения проблемы тождества слов для полугруппы G . О п и с а н и е а л г о р и т м а . Даны любые два сло­ ва С и 3) полугруппы ft , . . . , й п ; А< =Й* , л. = I , , , . . . , к!>. Возьшы полугруппу '<& , заданную образующими эле­ ментами , . . . , а„ и определяющими соотношениями А>| ,..., А к =Вк, С =Т> . Узнаем, изоморфны ли полу­ группы & и Если полугруппы изоморфны, то заключаем, что С! =Т> в полугруппе Gr . Если полугруппы не изоморфны, то заключаем, что C4V в полугруппе f t , Д о к а з а т е л ь с т в о . Если полугруппа ^ не изо­ морфна полугруппе f t , то очевидно, что С =*D в полугруп­ пе Gr . Если полугруппа , являющаяся фактор-полугруп­ по'* полугруппы f t , изоморфна полугруппе f t , то по теор е­ ме 4 следует, что слова С и D равны в полугруппе f t . - 7 - /