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

так же, как в работе [ б ] (с учётом того, что в ЕЕ С -пред-' ставленной полугруппе не могут выполняться равенства вида Р = S Р 7* , если S или Т негусты). Теорема доказана. Отсюда следует существование алгоритма, решающего проблему изоморфизма для полугрупп, заданных конечными FЕ С -представ­ лениями. В самом деле, так как определяющие слова обоих полу­ групп имеют длину не меньше двух, то изоморфные полугруппы должны иметь одинаковое число образующих и при изоморфизме образующие переходят в образующие. Тогда можно применить алго­ ритм из теоремы 2 . Заметим, что если не накладывать ограничений на множество определяющих соотношений, то существует несчётное число неизо­ морфных 2 -порождённых FEC -представленных полугрупп: П; = < а, в ; a 6 La = B a l B , L € I > - здесь I - произвольное подмножество множества натуральных, чисел. Легко вцдеть, что для различных 1Г и 1 2 полу­ группы /7 / и П1х не изоморфны. § 4 . Полугруппы с малым налеганием определяющих слов По-видимому, впервые методы теории графов для решения проб­ лемы равенства слов в полугруппах применил Е.В.Кашинцев в статье [ 7 ] . Там он установил разрешимость этой проблемы для довольно широкого класса полугрупп. Наша цель - доказать, что для полугрупп из [ ? ] справедлив более сильный результат - они являются ЕЕ С -представленными. Этому посвящена теорема 3, причём её доказательство является упрощением доказательства из [ 7 ] . * В теореме 4 рассматривается обобщение класса Е.В.Калшнцева. Сначала дадим необходимые определения. Пустое слово будем обозначать знаком Л Пусть П - конечно-определённая полугруппа: Г) = < а , , а г ,..., ал ; AL = BL, i- v F >. ( 7 ) fCy) = [ А (-} U [ Bi l - множество всех определяющих слов полугруппы. ОПРЕДЕЛЕНИЕ 3 f 7 J- С -4000 X называется кус­ ком, если найдутся такие С , = 2 ) X Е , Су = F X Н (возможно, С( = С у ) , что- 2 )2 F или Е ? Н • Цудем говорить, что слово X имеет правостороннее, лево- 61