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

Очевидно, что она удовлетворяет всем необходимым условиям. Теорема доказана. Легко видеть, что в F Е С -представленных полугруппах с рекурсивным множеством определяющих соотношений разрешимы проблема равенства, проблема делимости, проблема вхождения в конечно порождённую подполугруппу. Хотя теорема I полностью описывает класс F Е С -представ­ ленных полугрупп, в каждом конкретном случае неясно, можно ли задать на полугруппе подходящую функцию дайны. Поэтому пред­ ставляют интерес такие примеры функций длины, возможность за ­ дания которых на данной полугруппе проверяется эффективно. Мы дадим несколько таких примеров, но сначала заметим, что если полугруппа П имеет более одного определяющего соотноше­ ния, то иногда теорему I удобнее применять в следующем виде: полугруппа с конечным множеством образующих и рекурсивным множеством Т определяющих соотношений F Е С -представлена тогда и только тогда, когда существуют функции длины JV ,. . . , Sp на этой полугруппе, рациональные числа С ,, ... у Ср ( б,- >•. о ) и разбиение множества Т на непересекающиеся подмножества Т -~ Г , U T t U... U T p так, что выполняются условия: дая любого соотношения A i ~ если А; = 6 [ входит в 7} , то д ( А * ) - д ( B i ) = С( [ ( B i ) ~ Se ( А {) ] И s « ( B i j - S * ( A i ) = о при к * l . Тогда в доказательстве теоремы суммирование ведётся от­ дельно дая соотношений каждого множества 7 } ( (= и конечный результат имеет вид: d ( V ) 4 d ( w ) * C , S f ( W ) + Cp S p ( w ) . § 2. Примеры функций дайны Приведём некоторые прм!еры возможных функций дайны. Везде A i , Bi обозначают слова из определяющего соотношения A i * В; соответствующей полугруппы; 16 = { а п . . . , Лп ] - множество образующих. i] S ( Р) - д ( Р), - обычная длина. Тогда д ( А { ) = д ( В ; ) для всех t . 76