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

6 ) L ={t,c0,d0,...}. Если g архимедов элемент и (5) - его нормальная форма, то g допускает эффективную запись в виде g - wgtw 1 , где <p(g|2) = 2 ср(^,), a w записан в /-редуцированной форме: w~q„tu'q, ■t k)'qs ; gf —t*ri... Tjt *» С помощью алгоритма, действующего в Я, можно проверить, выполнено ли qt е М = gp(c0,d0>...), /' = 0,1,..., s. Если хотя бы для одного q. qt е М , то при всех натуральных х g* ( К . Если же включения выполнены, то проверяем, справедливо ли rt е М , i = 0,1,...,/. В случае положительного отве­ та g - wgjW1е К . В противном случае при всех х g* t К , так как если g ‘ е К , то g* е К , а тогда и g, е К , так как нормальная форма элемента g* есть х- кратноповторенная нормальная форма элемента g {. Пусть g =wg,w~l , g, е Н , т.е. cp(g 2 )<<p(g). Если q>(g) = 0, то g - g t е Я , и вопрос решается с помощью алгоритма, действующего в Я. Пусть <p(g) > 0, w = q0tUl... qs.,tu". С помощью алгоритма, действующего в Я, выяс­ няем, верно ли, что q, е М при всех / = 0,...,^ -1 . Если верно и для некоторого x e N g* е М , то g x е К . Если g* t М при всех х е N , то выясняем, будет ли <p(gy) <<p (g ) для некоторого у е N . Если нет, то при всех х g x е К , если да, то вопрос решается для g y, где у - наименьшее натуральное число, при кото­ ром <p(gy)<<p(g). Пусть .для некоторого i е {0,1,..., s -1} qx i М . Тогда если при всех х е N <p(gx) =<p(g), то g x е К . Если же <p(g*)<<p(g), го задача решается для эле­ мента g x. Осталось рассмотреть случай, когда сумма показателей любого из обра­ зующих группы G, входящего в Я, отлична от нуля. Пусть, L = {Я0, с0, , о , (Я) = а , сг^ (Я) = р . Отображение ¥ , определенное при помощи t - > y x " , р„->ха, с0-* с 0, ... 198