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

Если подслово t п слова u(_f н^изолироьано в мно­ жестве { 2 )t } , а подслово t ^ s x c 4 слова u z _t - изолировано, то так же, как и в предыдущем случае, харак' котика множества / W , СУ,п UL-t>n 1 оудет меньше характеристики W . Действи­ тельно, множеству подгрупп { 2>(1 принадлежат подгруппы ^ / ~ и 7-г,л О t e 'u %-tt A > гДе u "t-tл ^ ~ начальное подолово слова и г_( = ^ г-/,л t £"Kt е^ к л с * К *;'Г**+*а t e*+*Xj- <4-,,п В слове и г. ^ и ' { , 1л t £ "/Ct £*fSXC '/ ^(uj_f/[ f kisjtc') Используя слова и г_, , и г , cyj a п , можно подгруппу Ъ{ преобразовать в подгруппу %C/ . f е Наконец, рассмотрим случай, когда подело га ■- k*Sx<j u-i-i,n> L kf!x С с л о в U(_t , и г_, изолированы в {2)t } . Тогда у слов подслова 1У-'£ /л t £ , и 'г ч не изолированы в /А } . Поэтому мно­ жеству f i L) принадлежат подгруппы 2 >ii = a ^ / t £ " a t~ l "u'~'f u i-i t Sо t L гг'//, допустим, ЧТО t € ') = XC~') Тогда", используя слова и г_г , Uc~t , <-(? , Ctyi ui-i, п. • m m o подгруппу 3)г, преобразовать в подгруппуЭ^. Допустим, что либо 9 (и 'г_ 1 л ^ " ) < 9 ( ^ к*{хс'> ) ^ либо ^ ( ui-tA ^ ) <^ ( t ktSxc ') Тогда, так как Xj является слогом правой половины слова U i4 , то Ъ(и ^ , ) > 9 ( cxj n ut п ) Поэтому, если o(u'.f/lt£*)<^(t^k*sxc~Y)j то слово И,-.г заме­ ним словом гг/., = u t.t (cxJn ui-i,n)~'и 'г u~'_t л c ? ( <4-J Если b(u'i 4 ' A t * ) < . b ( t f ****€'*) и *(u'7^ t e") = Ь( t e*” j(c -<)t to 9(Ut., ) > 9fut.,j , и заменяем слово Ub i словом гг/., =Uz,t <хг (и,-., U^,'t n x j^ c~1) причем Щи 'г -/)к & ( Поэтому в каждом аз случаев лемка справедлива. 6 V) с 1 - Если Xj , то данный случай аналогичен , поэтому, предположим, что У/=Х . Тогда к множеству W присоединим CXjn С~' . и так как С - подслово неизоларованн- и де;«о* половины некоторого и -символа, то среди подгрупп /Л} содержится подгруппа сас4 , поэтому характеркотика ук.'же- 33