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

одного из условий: ( о(, ) являются ли и, ut ( V, irf ) граничными метками кольцевой R - диаграмм М вада 2 °; ( схх ) являются ли слова U , и , (V , V, ) граничными метками R - диаграммы М вида 1 ° . Д 7 Ш этого к словам и , и , { v t i r ) (лвнна 4 1 ) приме­ няем алгоритм, выясняющий сопряженность слов в группах с условия­ ми С ( 4 )& Т ( 4 ) , используя в качестве шокества R симметри- зованное множество R определяющих соотношений группы Q- ; ( а 3 ) заменяя u t ( гг, ) словом u ' , ( v / ) i u ,£ L и ,' (is , Ж г г /) специально R - приведеншал о условием S ' ; выясняем для и. , и / , ( V , У / ), являются ли они граничными метками кольцевой R - диаграммы И .вида 3°. Если ни одноту из условий (Ы, )-Со1л) пара U , U , { i f , V , ) не удовлетворяет, то образуем пару и , и». ( V , ггл ). *' Предположим, что слова U , и , ( v , v f ) удовлетворяют од­ ному из условий (с * ,) —(о(3) . Тогда, заменив U, ( гг, ) словом и ; ( к \ и , S u 't y Q ir /) специально R - приведенным с условием S ) образуем упорядоченное множество W ( u ' ) ( W ( v / ) ) и рассматрива­ ем пару u f t и „ ( v ,\ Щ,) , где Ut t (V ,,) - наибольший элемент сог­ ласно рассматриваемой упорядоченности в W (u ,)(W (v ,)) . Применяя для слов и , гг описанный процесс, через конечное число шагов получим слова и , гг , сопряженные в группе (? соответственно слова :,1 и , гг , являющиеся специально R - приведенным: и удовлетворяющие условию S , на которых рассматриваемый процесс останавливается. Если l u l ^ / V l , то и , г/ на сопряжены в (? и, следователь­ но, искомая R - диаграмма М для них не существует. Пусть | й | = | ^ 1 . Рассмотрим множество слов U - { ^ i . каждое из которых является специально R - приведенным, обладает условием S и имеет длину равную \ и \ . Множество U содержит слова и , >г . Образуем из слов, принадлежащих I / , всевозможные пары (Щ, W j ) I #5 r-r . Из образованного множества пар (uri t и г,-) отбираем все пары, которые удовлетворяют одному из условий ( ы , ) - - (о!3) . получаем множество (/0 . Проверяем, содержит ли ££ пары о и и с V . Если не содержат, то и -Z' Р 5 . В противном случае пилением, можно ли из множества пар С/а составить последо­ вательность пар следующего вида: ( и , ^ (иг- г Щ. ) (Щ >гг) Если это возможно, то и~ - гт в Q- и, слодоват^льно, для и , V существует рокоман R - диаграмма М . В противном случае -н ет. Jioj.n.ifi доказана. СО -