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

ДОКАЗАТКйЬСТЪО . Если все определяющие слова полугруппы удовлетворяют условию К ( z ) , то всё уже доказано в теореме 3. В противнем случае для любой минимальной сети над полугруппой П справедлива лемма 4 . Пусть U - V в П . Существует минимальная п. э . п. вида ( 8 ) и минимальная приведённая сеть $ т такая, что Ч П Л - и , I/. Тогда S ( v ) - ' S ( U ) [ -Г ( T j ) - S f T y - J ] = =f [ S (T t ) t S ( reJ ] г| [ S(TK) - S(TK_,)] . (12) Первое слагаемое в правой части (12) - сумма по всем таким ин­ дексам I , что в сети $т *С-е имеет общие рёбра с Т 0 (таких индексов не более, чем д ( и ) ) , а второе слагаемое - сумма по остальным индексам. •Обозначил К = m a y [ S (A't )~ Применим лемму 4: S ( v ) - S ( u ) 4 д ( и ) - К + M - Z С - с/(Т „)}. Учитывая, что £ ( V) » О , получим: 1 $(гс) + д(гс)-к] ^ Z [</{тк_г) - с/(тм)] . да) Теперь оценим количество рёбер в t~m . e f ( r m ) - с / f a ) = t L с / f a ) - ) ] = • f W f 7*) - S f a J ] - c / f r j ] . Здесь опять в первой сумме учитываются э. п ., затрагивающие исходное слово 1C , во второй - остальные. Тогда,по лемме 4 и учитывая (13), имеем: с / ( г „ ) - eff a ) 4 л д ( и ) - 2 [ ^ f a . Y) - с / ( т « ) J 4 * 4 г д ( и ) * ( S ( a ) + д ( к ) к ) , Отсюда получаем (как и в теореме 3 ) , обозначая L - rn a y д(С^), что d ( v ) 4 [ z д ( г с ) *■-£- ( £ ( и ) + д ( и ) - к ) *■ /7 ■L + д ( м ) - Отсюда следует утверждение теоремы. Заметим, что теоремы 1 ,3 ,4 и примеры функций длины без труда переносятся на полусистемы Туэ, при этом можно от­ бросить некоторые ограничения. Часть результатов этой статьи докладывалась на семинаре по алгебре при Тульском пединституте. Автор благодарит руко- 90