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

Пусть 3 ( i t ) - l 4 + i t > притрем i t букв из слова I t затрагивается элементарными преобразованиями ( 8 ), а. не затрагивается. Тогда ясно, что не более дут могут иметь общие рёбра с "Се , и по лемме 2 в этом случае d ( r e ) - d ( T t . , ) 4 Z . д , я остальных индексов по той же лемме 4 ( X t ) - c f ( r k j 4 о . Таким образом, из ( l l j получаем d(T-m) - с/(т-с) 4 z / , . Так как 7" в сети S, состоит из одного ребра, то с / ( ъ ) ~ 4 . Значит, с / (nrm ) 4 Z i 4 + / . Каждое ребро £t- в Тт , не входящее в 7» , имеет своей меткой часть некоторого определяющего слова Су , поэтому д ( Ч ( £ \ ) ) 4 L . А длина меток всех рёбер, входящих одновре­ менно в Т 0 и в , равна Сг . Получаем d( v ) 4 ( Z t 4 +Y)-L+ е г . Так как можно считать L * О , то отсюда следует утвер­ ждение теоремы. Теорема 3 получена автором независимо от Е.В.Кашинцева, который доказал её гораздо раньше, но не опубликовал. Заметим, что для-рассматриваемых сетей справедливы аналоги лемм 16,17 [ 9 ] , поэтому оценку из теоремы 3 можно понизить. ' Теперь определим класс полугрупп, к которым применимы мето­ ды теорем I и 3. Опять { Су} - множество всех определяющих слов полугруппы. Слово X назовём куском, если оно является куском по определению 3 или если A" s Ct- — Су при I •* / .. Будем говорить, что слово X имеет правостороннее, левосто- . роннее, внутреннее, полное вхождение в определяющие слова, если найдутся определяющие слова соответственно вида: В X j X Е ; F X Н ; X , где В , Е , F , Н непусты. Слово X имеет односторонние вхождения, если либо все его вхождения левые и полные, либо все вхождения правые и полные. ОНРЕДьЛЬИШ 4 . Если С = Q, . . . - произ­ ведение кусков, то будем говорить, что это произведение не явля­ ется плоским, если для некоторого L ( Y 4 L 4 t - - f ) Q i имеет только левые и внутренние, a Q i n - только правые и внутренние вхождения. Если такого L не существует, то произведение плос­ кое. ОЫШЛШШ 5 - Непустое определяющее слово С удовлетворяет условию: 85