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

и в : * ( в * Г и н . I I ) Рассмотрим конечные последовательности натуральных чи­ сел: ) • •• > > ( 4 ) S , , S a , . . . , S n . (5) Будем говорить, что (4 ) входит в ( 5 ) , если для некоторого индекса / S j > t i , Sy ,, = t t } . . . , ■£,'+*•-*= i K.Y) Начальная подпоследовательность последовательности (4) - i t , p , где C < l < K , 0 < p . < t t ^ . Аналогично определяется конечная подпоследовательность.- Если Р = (tfr' в * ' -, • , где Lj * l j +Y , $ е > 0 ) то S ( р) - число вхождений последовательности (А) в после­ довательность S Y, .. у S n ■ s ^ Условие: если А( - . . . / й / - в г, - , то а) Л,- , начинаются на одну букву и кончаются на одну букву; б) любая собственная конечная (начальная,) подпоследователь­ ность последовательности (4) совпадает с начальной (конечной) подпоследовательностью последовательности S f ; . . . , о к тогда и только тогда, когда она совпадает и с начальной (ко­ нечной) подпоследовательностью последовательности . Некоторые из приведённых здесь функций длины являются част­ ными случаями других, но более просты в применении. § 3 . Изоморфизмы F E С -представленных полугрупп Очевидно, что в FE С -представлении не могут встретиться . определяющие соотношения веда А - / и Qj - T d j P * Если же есть соотношения вида Ctj = Т , где Т не содержит Q ; , то можно удалить Qj из множества образующих, используя прео­ бразования Тице. Таким образом, в дальнейшем будем считать, что в F Е С -представлении все определяющие слова имеют длину не меньше двух. Заметим, что для этих полугрупп выполняются все результаты статей [ 4 , 5 ] . В.Г.Дурнев в [ 6 ] доказал разрешимость ограниченной пробле­ мы изоморфизма для полугрупп, заданных представлением с равно­ длинными определяющими соотношениями. Этот результат легко . переносится на весь класс F Е С -представленных полугрупп. TbOFtirtA 2. Пусть полугруппа П задана конечным 79