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

Пусть /77 > t >■ f . Если t < m~- f , то рассуждаем, как в случае I , и приходим к противоречию. Значит, t = т а) При т - Я из определения полугруппы получав!.?, что С - кусок, имеющий только полные вхождения. Но так как t = / , то в этом случае должна входить в некоторую нижнюю дугу />„ , не совпадая с ней, а тогда С не будет полным кус­ ком. Получили противоречие. б) Пусть т ъ 3 , t = /w- у . Тогда либо произведение С * не является плоским few. случай IЛ либо и ^ имеют только односторонние вхождения. Тогда, имеет только правые и полные вхождения. Но так как правый ко­ нец ^ У ц не совпадает ни с одной вершиной из Sy , то является собственным началом ребра £ , входящего в некото­ рую нижнюю дугу yS* . Тогда у ( 6 ( 1 = Q t имеет либо внут- реннее, либо левое вхождение. Получаем противоречие с одно­ сторонностью Q t • Следовательно, т a i . З) Ни один конец «бу+у не совпадает с вершинами сети V В этом случае о/ (Ту) - (/(Ty+f) +2* t - / • Пусть /77 > i - / ^ О . a) т = У , t =' S . Следовательно, по определению полу­ группы, С - кусок, не имеющий внутренних вхождений. Но так как ни один конец •‘v +y не совпадает с вершинами сети Sy , то некоторая нижняя дуга - f a К . Г< и S i - непустые пути, поэтому С имеет внутреннее вхождение. б) / 77 = 2 , t £ Z . Если t = / , то, по условию, £ име­ ет только полные вхождения, а тогда концы ^-у+< должны ' совпадать с некоторыми вершинами Qj . Пусть , С* . . В этом случае либо произведение Q* Q t неплоское (cf!. случай I ) , либо хотя бы один из кусков Q y , Qi имеет только односторонние вхождения. Тогда, рассуждая, как в случае 26, по­ лучим, что ни Qi , ни Qz не могут быть односторонними. b) tr> } 3 . Сразу отбрасываем случаи, когда произведение С ■ Q( не является плоским. Остаётся случай, когда хотя бы один из нусков Qf , Qt имеет только односторон­ ние вхождения. Опять получаем противоречие, как в случае-26. Следовательно, т ^ t - S ■ Лемма доказана. ТЕОРЬмА 4 . Полугруппа (7 ), удовлетворяющая усло­ виям 1 ,2 ,3 , является С -представленной. 89