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

A tj Х {/ Bt-j = £ ty K v A y - определяющее соотношение ('или A(j xij s Ccj Y(j S)t-y и существуют определяющие соотно­ шения вида ACj Xij &(j - Н , И ~ c tJ Ycj ® гу ) ; 3 . Для любого е Al f , Ci f ) B>i x . t £>{к . a yi ; 4 . Для любых l , j ( ■ fi j < к , ) ровно один из кусков пустой и ровно один из кусков i j + у пустой J 5 . Для .щобых L , J ( 4 < У < K i ) &IJ ~ Ф i j & A I J H — С i j + i , либо B ij = С i y i-i Я £>ij - A i j +4 > 6 . Для любых 1, J ■■■ x c j &ij ~ K j Y ijSD y , A tJ X i j . . . Xtk( - C i j Y ij... Yik' ДОКАЗАТЕЛЬСТВО. Применим индукцию по числу К элементарных преобразований от А до V . Если К - О , то лемма выполняется. Пусть лемма верна для некоторого к & о и пусть ( к * 1 ) - е элементарное преобразование заменяет £ на £ , I где £ - F определяющее соотношение. Рассмотрим всевозможные ‘ случаи. 1 . Е содержится в некотором / i j . Тогда £ становится новым и индуктивный шаг проходит. 2 . Е содержится в некотором 7/ . Возможны следующие под­ случаи . 2 . 1 . Е содержится в некотором У ц , не совпадая с ним. Тогда £ - ку сок, что противоречит определению полугруппы. Следовательно, этот случай невозможен. 2 . 2 . Е — Y ij . Если К,, £ Мп , то Е - кусок и опять приходим к противоречию. Если V,'y е Мп , то CtJ = YD(J s Л . Тогда либо A,J Bij- * F - определяющее соотношение, либо A ,j Xlt/ BtJ э Г (это еле,дует из симметризованности АУП ) . В этом случае F играет роль нового Ку . Из Индуктивного предположения следует справедливость всех утверждений леммы. 2 . 3 . £ п ересекается с УС/ и Ку+ y , но не пересекается с другими Yif. . Если нй К> , ни ч не содержится в £ , то £ состоит из двух ку сков, а это невозможно. Пусть Р - Y ■Y л У = К— Y п С - 7(у ’ ' lJt -4 ' 4* 1 ■ (симметричный случай рассматривается аналогично). Если то £ = Y,j Y\j f i . Поскольку один из кусков & ij , п уст, то либс l tj Ytj , .либо К / 4 E>ijt1 является произведением не бол ее, чем двух ку сков, что невозможно. Значит, V , . t А , К , ^ \у* t j ti - кусок, а п у не может быть куском. Поэтому 70