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

На любой полугруппе можно задать функцию длины - например, обычная длина слов является функцией длины. В некоторых случаях функцию длины можно задать так, что S ( B i ) >S ( A i ) . ТЕОРША I . Для полугруппы П с конечным множеством образующих элементов и рекурсивным множеством определяющих соот­ ношений представление ( I ) является F ЕС -представлением тогда и только тогда, когда существуют функция длины S на П и рациональное число С >, О такие, что для любого определяющего соотношения A t = й/ полугруппы П выполняется условие: d ( A i) - d ( B i) = c [ S ( B i ) - S ( A i ) j . ДОКАЗАТЕЛЬСТВО. I ) Допустим, что существуют функция длины S и число С , удовлетворяющие условиям. Пусть W - произвольное слово, S ( w ) = t и V - W в П . Существует последовательность элементарных преобразований (п. Э. П.) S W = W » - * К К э 1 / . (2 ) Обозначим через бу число элементарных преобразований (э. п.) веда РBjQ PAj Q в (2), через /у - число ». п. веда PAyQ— РBy Q в (2), l y = Ру • Рассмотрим сумму по всем таким индексам у , что в п. э. п. (2) имеется либо подстановка Ау , либо By ~~ Ау . Так как функция длины неотрицательна, то X e y [ s ( B y ) - s f A j j ] v< S(By ) - S(Aj ) l . Отсюда Z ^ [ S ( B y ) - S ( A J ] * t . fy) Ясно, что * d ( V ) - ' d ( W ) + Z J-j l d ( Ay ) - д ( в у ) ] . . Учитывая (3) и условия теоремы, получаем д ( у ) 4 d ( W ) + c t . Поскольку полугруппа П конечно пороадена, то произвольное слово W равно конечному числу различных слов, и, следователь­ но, (i) - F E C -представление. 2) Пусть (I) - F E C -представление. Тогда для любого слбва X существует равное ему слово X максимальной длины. Опреде­ лим функцию длины следующим образом: S ( X ) - d ( X ) ~ d ( X f . 75