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

G f - < G , t.-.reia, По теореме I в группе Q* разрешима проблема вхождения. Покажем, что существует алгоритм, позволяющий в группе G-* вы­ писывать образующие пересечения любой конечно порожденной подгруп­ пы Н G* с U£ : , £ = * / , • Приведем образующие подгруппы И к специальным: , где S порождена подгруппам!: Поскольку А ■ то на основании леммы 3 н т ь щ ю щ - , где ( ^ ) < £ , если среди подгрупп ряда (7) содержится такая; в противном случае Н П и е := Е . Пусть W 6 Gf - произвольное слово группы . Пока­ жем, что молено эффективно выяснить, пусто или нет пересечение ьгНП U$j , где Используя алгоритм 01 [I] представитель класса смежности игН выбираем наимень­ шей длины. Если игв =1 , то urHflUq^ULJflUsj , где (M f)<Gr -под­ группа ряда (7 ), соответствующего подгруппе Н . Если L(w0)>t) то vrHnUj * 0 . Если L(w0) ^ f и ига eGr , то и гН О О ^щ (Щ О и ^ у где (М{) < Gr , то есть задача свелась к аналогичной в группе Пусть L(w0)& I и W~0 содержит бугшу t , . Слово ига по­ лучилось из № применением к нему алгоритма O t [ I ] , укорачи­ вающего его длину с помощью слов из подгруппы H=gfi[JUC!S ) , Wc может иметь один да видов: uro^ k i ^ b t * zf ur0= k ^ & } W0 ~ B Где в первом и во втором случаях,., если £,= / 1, то к<*Ц и 8 -представитель правого класса смежности группы С? по m od Ц , а если £±~1 , то Ae'/J ( U ^ я д - представитель правого клас­ са смежности Q по тЫ (Ч ,($)). Согласно действию алгоритма 01 [ I ] , конечное подслово W0 , в частности пустое, является ко­ нечным подсловом правой половины некоторого ИГ* , принадлежа­ щего специальному множеству образующих Н . Покажем, что не существует слова U.1U!L...U.n_e ^ l 0 ^ o , S ) такого, что w0Ur ,.Une Cr . Допустим противное. Тогда L(u^tLl...iJTi)*l и отсюда ц „ ) £ 2 . I . П у с т ь и l ( U t ...Ил ) я2 , тогда Ц и ) * 2 , i= t,a - 9 -