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

ф( 9 |) = ф(? 2 )> то Ч\ ^ЧР(Чз) тогда и только тогда, когда q, = q f ; если ф ( 9 |) > ф (^)» то ПРИ < р (?2?|)’ 4 ф ( ? 1 ) - ф (?2) и при <p(q]'q,)*<p(q,)-(p(q1) q^egpiqi)- Если же 9 (4 'i4 i)-v (< h )-v (4 i)> е е { - 1 , 1 }, то 4i е gp(4i) ^ Чз =ЧзЧз е &Р(Чз) и рассматривается слово q3 меньшей длины. Вопрос о распознавании нетривиальности пересечения можно решить так: пусть <р( 0 , ) = т , <р (q2) = м>. Находим натуральные s и t такие, что ms =nt и s + t минимально с этим свойством. Тогда <р( q‘ ) = <р( q \ ) . Если q]*q':, то gp(ql)C\gp(,42) = {])- 3. Пусть g, и g 2 - неархимедовы. Можно считать, что g t g2 = wqw~', q е Н . На основании следствия 2 можно утверждать, что существу­ ет эффективная процедура, позволяющая определить, есть ли натуральное х, что g ’ е Н . Если такогох нет, то gp(g,) П gp(g2) = {1}• Если для минимального х g 2 е Н , то вопрос о нетривиальности пересечения gp(g|)flgp(g2) и справед­ ливости включения g | 6 gp(g2) сводится к вопросу о нетривиальности пересе­ чения gp(g,)P\ g p (g \) и справедливости включения g, € gp(g] ) , которые ре­ шаются с помощью алгоритма, действующего в Н. Если каждый из образующих группы G, входящий в R, имеет нулевую сумму показателей, то решение сводится к рассмотренному случаю с помощью стандартного приема, использованного в теореме. ч... Литература 1. Линдон Р., Шупп П. Комбинаторная теория групп. М.: Мир, 1980. 200