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

F E С -представлением: П - К &/>’ ••> j ~ DI ) L - 'f, К > . Существует алгоритм, позволяющий для любой конечно-опреде­ лённой полугруппы Н с не более чем образующим определить, изоморфна ли она полугруппе П . ДОКАЗАТЕЛЬСТВО, Пусть Н • < 4 , . . . , ip ; Су = Я у , _ у ' « Т Г г > , р < / г * / и пусть f - изоморфизм Н на П , f - обратный изомор­ физм. Тогда элементы f ( f l i p) порождают П . , Поскольку все определяющие слова полугруппы П имеют длину не меньше двух, то { Q , , . . . , Qn I - С Ч 1 К ) > - - ч f l i p ) ] - Тогда р ^ п . Остаётся две возможности: р = п и />=/г<-у. I ) Пусть р = П. . Тогда существует г г ! различных отобра­ жений i ff , fz> ■■•) f n ! множества ( i f , / л } на множество { O f j . . . } Cln j . Алгоритм состоит в следующем: для каждого отображения f t , / = « £ £ / проверяем, выполня­ ются ли в /7 равенства f t ( Су) - f t ( 2 >у) для всех J ('при этом пользуемся тем, что в FEC -представленной полугруппе разрешима проблема равенства слов,/. Если ни при одном отображе­ нии f t эти равенства не выполняются, то Н и /7 не изоморфны. В противном случае некоторые ft- можно продолжить до гомоморфизма Н на П , и тогда для этих f t прове­ ряем, можно ли продолжить до гомоморфизма П на И об­ ратные отображения Tft , т . е. выполняются ли в Н ра­ венства f t ( A i ) - Lf] ( S t ) для всех I . Эту проверку можно эффективно осуществить по следующей очевидной лемме: ЛЕШ I . Пусть Нж< i / 7...ffn i Cj *2>у , j € J > - Сб ) конечно определённая полугруппа} П = < а 0 . . . , а п ; A i = Bt- , L e l > ~ F £ С -представленная полугруппа и некоторое отображение множества / п } на множество [ Q < <7Л ] можно продолжить до гомоморфизма Н на П . Тогда (б) - F Е С -представление для Н , поэтому в Н разрешима проблема равенства слов. _ . Если ни одно из ft не продолжается до гомоморфизма, то Н и П не изоморфны; если продолжается, то искомый изоморфизм найден. 2) Случай, когда р * Л + / , рассматривается точно 80