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

2. Пусть W0--h .t£l , & . Если пустое слово либо & является конечным неделовом некоторых u / f из специального множества об­ разующих подгруппы Н , то в этом случае любое произведение U T o U f . u ^ содержит букву t , , а следовательно, игНП Ue z = 0 Пусть t £<в - конечное подслово некоторых w f из специального множества подгруппы Н . Допустим, что и ,.,. и п , /.( u ,...u n )=-2J является произведением простых слов гг , , ггх Л Сьг; ) ~ / , i ■ Чтобы в произведении urc yf 2/i. было сокращение, необходимо, чтобы гг, = в ' , wK =t ~£’В* *, где , A e U f , если £ , - / , и h «■ % (и ,) -ъ противном случае. Однако, это невоз­ можно, так как в этом случае длину и / £ можно было бы сократить, что противоречит свойствам специального множества. Аналогично этому невозможен также случай: V, =&'t~0 , ъг^=В'' ,где h е V f , если £ , т/ ,и h « W ( V ,) t если £ • - / . Рассмотре­ ние такого случая показывает невозможность и случая L(ut ...u /l) * , i . Пусть 1(и^ ..ип)= 2 л U,... и а _ простое слово. В этом случае произ­ ведение и, ., и п содержит один и только один и -символ слого­ вой длины 2, то есть нетрансформу четной длины, причем она может быть только вида B 'h . Поэтому, чтобы было urc ut u n €<*, слово и ,...и п необходимо должно иметь вид: и , ( 6 ' h t ' £<В ") и }} где U , = / 9 иь = 5 <3/,;Чоднако в этом случае мы получаем противо­ речие со свойством ( i V ) определения 2. 3. Пусть ur0 ~ B t £*- . Если произведение и ,... и п после сокращения имеет вид , то иг0 и,.. u n £Q . Отсюда следует, что L (u,.,. и п ) « / , но тогда У , = 1 , то есть и,... и п - простое слово. ЬШжество нетрансформ Мд подгруппы рр- №<>, S) VH9 должно содержать нетрансформы С €* в' и' k t , где А &% (C/1) i так как в противном случае алгоритм 6Т преобразовал бы слово иге в слово в " „„поэтому данный случай невозможен. Отсюда на основании теоремы 2 в группе G * разрешит проблема вхождения. Пусть В'каждой группе .{?* , , разрешимы: (I) проблема вхождения, (2) проблема пересечения любой конечно порож­ денной подгруппы Н < с каждой из отмеченных подгрупп , U y , • (3) проблема пересечения классов смежности лю­ бой конечно порожденной подгруппы Н<Сг* с каждой из подгрупп Uj , Щ . Покажем, что проблемы (2 ), (3) разрешимы е груп­ пе Q * . Поскольку и ~