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

есть гомоморфизм группы G в группу С =< у,х,с „,...; R(ух~е,х°,сп,...). У : G -> С есть вложение и слово wx(t,b0,c0,...) e K тогда и только тогда, когда w*(yx~fi,х а,с0,...)е.Ч '(К ) (см. [1]). Как в рассмотренном выше случае, наша проблема разрешима в группе С относительно подгруппы Л/, порожден­ ной множеством {х, с0,...} . Так как М свободно порождается этим множеством, а подгруппа 'К(К) свободно порождается множеством {ха,с 0,...}, то проблема разрешима в М от­ носительно У( К ) , а тогда и в С относительно У (К ). Следствие 1. Пусть G =< t,b0,c 0, ...; R > - группа с одним определяющим соотношением, R - циклически приведено, о, (/?) = 0, (1) - представление груп­ пы G в виде //МУ-расширения, (5) - запись произвольного элемента g e G а нормальной форме. Существует алгоритм, позволяющий определить, найдется ли натуральное х, что <р(g*) <<р(g ) ■ Следствие 2. В классе групп с одним определяющим соотношением алго­ ритмически разрешима проблема вхождения в циклическую группу и проблема распознавания нетривиальное™ пересечения циклических подгрупп. Доказательство ведем индукцией по длине определяющего слова R. Ес­ ли R затрагивает только один образующий, то вопрос ясен. Пусть R затрагивает по крайней мере два образующих / и Ь0, и о,(Л) = 0. Тогда G представима в виде (1). Пусть g ,,g 2 e G . Если <p(g,) = <p(g2) = 0 • то £i>g 2 и применим алгоритм, действующий в Н. г-нг 1 1. Если один из элементов g ,,g 2 архимедов, а другой - нет, то какими бы ни были x ,y e Z \{ 0 }, g x, * g], т. е. gp(g,)Dgp(g2) = №• 2. Если g, и g 2 - архимедовы, то g, , g2=w2q2w]' , где ф(д ,)2 = 2ф(д,), i - 1,2. Если w, * w 2, то g p ^ J f l g p ^ ^ W - В противном случае рассматриваем qx и q2■ Вопрос о справедливости включения qt е gp(q2) решается очевидным образом: если <p(?i) < ф(?2)> то Я\ £ ёР(.Чг)> если 199