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

где Н -< b,,...,bs,cl,d i,...(i 6 2); P = l> , (2) т и s - соответственно минимальный и максимальный индекс образующего, в действительности входящего в Р, длина слова Р короче длины R. Х=<Ьх ... b,_i ,cl,dl,...(ieZ), (3) H=<bTtl,...,b„c(,d„...(ieZ), (4) t b f ' = i j+/, j - т , i - l , tcf4 - с м , td,t~'=dM, .... »eZ. Л"и У - свободные группы. По индуктивному предположению, для любого h e Н можно эффективно определить, существует ли х е N , что hx eQ , где Q - подгруппа группы Я, по­ рожденная рекурсивным подмножеством образующих группы Я, и для любого элемента g е G может быть эффективно найдена его «-редуцированная форма относительно ЯЯЯ-расширения (1). Пусть g записан в «-редуцированной форме g = g / 'g , L « ‘*g„ (5) cp(g) = п - число вхождений «в нормальную форму (5). Возможны следующие случаи: a) L = {б 0 ,с0,^ 0,...}. Тогда К = gp(L) с Я . Если g архимедов относи­ тельно функции ср, то для любого х е N g ‘ ( Н . Если же g неархимедов, то g можно представить в виде g = wqw ~‘, q e H aw записан в «-редуцированной форме. По индуктивному предположению, для элемента q можно эффективно определить, существует ли х е N , что qx е Х или / е Г , т.е. можно эффек­ тивно ответить на вопрос, существует ли х е N , что <p(g*)< 9 (g ). В случае от­ рицательного ответа для всех натуральных х g x ( К . В противном случае на­ ходим наименьшее x e N , что <p(gx)<<p(g) и задачу решаем для элемента g; = gr . Ясно, что если gf е К , то g ” е К , а если gf £ К при любых у е N , то g ‘ £ К при всех z е N . 197