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

Если в слове и , ..М п содержится U - символ такой, что • • )~2, to Иг .М п - простое слово; если ( V L ) ( l(U - ) ) n , то Uy...U-п является произведением простых слов [ I ] , каждое из которых ддашы * I . ^ . Допустим, что пустое слово, либо ™ , либо 8 Г * является конечным подсловом правей половины некоторых l u f из специаль­ ного множества образующих подгруппы Н . В этом случае любое произведение и ^ и г ..ип будет содержать букву t f , а следователь- „о. ш Н П Ц . , - < * ^ Пусть ПОПОЛОВО слова Щ, является конечным под- „• 'оо., ,,..о-оИ половины некоторых из специального множества образующих подгруппы Н . Залетим, что средни специальных обра- зутощлх подгруппы Н -$ р -№ t>,S) не содержится ' f i t ,гд е h.€ tff (U^)> так как в противном случае алгоритм 01 преобразовал бы слово Щ, в слово h f 8/ , ‘ dL f ). Допустим, чью слово Ur ..Un ,L(u...Ur^*2t является, про­ изведением простых СЛОВ LLf U-n~Vt ^ • ВДб L(V,)$1, . Для того чтобы было Циго ц и л ) * 1 , необходимо, чтобы У ъ либо щ ~ t 't~a< . Первый случай невозможен, так как тогда алгоритм 01 преобразовал бы в слово V2 =B" , И ДЛЯ УСЛ0В1!Я ZiTcUt . . . , где h'^O i . Однако М п еСг Во втором случае необходпмо, чтобы этот случай токе невозможен. - . Ы ). Допустим, что слово и г ..и п простое. Тогда оно содержит ш МНОЖИТОЛЬ U>L , Ш 0 * 2 , Vj+L , L ( U j H i , и ( V i ) ( l ( u r . . a i_) u i ) ^ m a x i L ( a r ..u i 4 ), L ( u . i )}> г < с * п ) . Допустим, что и - символ слоговой длины 2, содержащейся в произведении u r ..un ~ v имеет вид . Тогда V U ,a l B 'r e'B * Цф , где U2= B % Однако это невозможно, так как множество нетрансформ JU0 под­ группы fyl(JU0f S ) содержит нетрансформу £'4а В"' , у которой t ^ - изолированная левая половина, что невозможно. Пусть .и цг=и4( f £ie ' t? 'B " ) и 3 , где -трансформа, либо и f —< . Но первый случай противоречит ( £ v У свойству специального множества, а второй - ( I ) -му: наруша­ ется условие изолированности закрытой левой половины нетрансфор- мы u * t *в'С в!В" в специальном множестве. Случай невозможен, *так как в этом случав произведение иг0 гг содержит tf . Случай Ц и г ,.и п ) - 1 аналогичен случаю ( ol. ) и тоже невозможен. _ 10 _ )