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

i v ) пусть itre= t '1Пл 1 * ,...1рчг{ 1**- ^ t f ~liur ... t \ 4 UTj- t y'rtui t * t V то не существует слова t Kr{u... " 9 - слова из е с ж u r * f % t * i W . , r ' f uf . , £r ± < > SmU? t b I r U 4 h * ij7 tM W ik ~ r f} необязательно различные, Г - начальное подслово закрытой левой половины^* - начальное подслово занрытой левой половины - hf w « V .b « T » > • ‘- T u l<2P ; " Л ,Т0 or. £^?= /"% «} ^ ... ^ ^ ^ lUj -: В работе (I) доказана , , . * т е о р е м а 2. Пусть V V ,t ‘ < f ( W > - Н М - расширение группы б5 с помощью изоморфных подгрупп Ut , Щ, и фиксированного изоморфизма Y: У(С / / ) = & / . Если Ц , ^ обла­ дают условием максимальности и в группе & разрешимы: (1)проб- лема вхождения, (2) проблема пересечения классов смежности любой к конечно порожденной подгрршы Н<@е с каждой из подгрупп и , , ич (3) существует алгоритм, выписывающий образующие пе­ ресечения любой конечно порожденной подгруппы H<Q с кгаадоЙ из подгрупп Ut , Urf , то существует алгоритм, преобразующий любое конечное множество слов группы (г* в специальнре. . Таким образом, мы можем предполагать, что образующие конечно порожденной подгруппы Н группы* <? образуют специаль­ ное множество. « .. ' „ Разобьем множество к * f /7 на подмножества следующим об­ разом: трансформы о одинаковыми крыльями об”единим в подмножество А . и и к , все нетраноформи из об"единяем в множество М а ; каждое множество , / * i * k , порождает подгруппу: ( M J - ,.ГПгс t ' A , Ц f S t . .Гн t в,‘ , где mOt t f ; f -li • ± 1 ; - подгруппа группы Q , порожденная ядрами трансформ с крыльями '**{.. fhc, l * . Подгруппы (M i) упорядочиваем по длинам крыльев порождающих траноформ: I ( А , ) * ( м о < 0 < ( м ^ ) (5 ) I е м м а I ( I ) . Пусть группа (г* удовлетворяет условиям теореш I . Тогда существует алгоритм, преобразующий ряд (8) в ряд ( A f ) ** ( А л ) * • • ■ • * X ( 6 ) О —