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

ныв соотношения выполняются одновременно, то искомая R -диаг­ рамма М. построена. Если ни одно из соотношений ни для какого a t из А( не выполняется, то искомой R - диаграммы М не сущест­ вует. ’Пусть одно из указанных соотношений имеет место, например, первое. Тогда, заменив множество Af на A ^ { A f \ 0 -t }, о.^ на Q t , применим указанный выше процесс к элементам сг , а ^ и . В результате через конечное число шагов ш сможем установить существование указанной в лемме кольцевой R - диаграммы. Лем­ ма доказана. Пусть - кольцевая связная минимальная R - диаграмма вида 1° сопряженности слов и , гг группы G- Артина (Коксетера) большого типа. Тогда, заменив в М каждую область Я , r e _ граничная метна 55, связной односвязной минимальной /?- -диаг­ раммой М , получим_кольцевую связную минимальную R -диаграм­ му М , где R ={J'_ j R ij - сиьметризованное множество определяющих соотношений rpynifci G- • ^ __ Л е м м а 41 [ 2 ] . R - диаграмма М , полученная из нольцевой связной минимальной R - диаграммы Г 1 вида 1 ° сопря­ женности слов и , U группы G Артина (Коксетера) большого типа, где и , гг _ специально R - приведенные слова, удовлет­ воряет условиям С (4 )М Т (4 ). Л е м м а 42. Пу'бть G- - конечно определенная группа Ар- тина (Коксетера) большого типа. Тогда существует алгоритм, поз­ воляющий для любых U ,V eG - нетривиальных специально R -приве­ денных слов, удовлетворяющих условию S , установить, являются ли они граничными метками некоторой кольцевой связной минималь- „ ной R - диаграммы М . Д о к а з а т е л ь с т в о . Пусть слова и , V , удовлет­ воряющие условию леммы, сопряжены в (? . Тогда существует коль­ цевая связная минимальная R - диаграмма М сопряженности слов U , гг . (Будем предполагать, что'области М не являются ( S - i ) - областями. Рассмотрим два множества слов в Gr : W (U ) = { U ‘ j t' - f j / , W (v) “ f V jji-jp y ', U f t W (u ), V<?W (v \ где каждое олово из W (u ) и W (v ), не равное единице в G- , является циклически приве­ денным в свободной группе, Vu± е W ( и ) : | U i l «= | u ) и ]/ir- е W (v ) • | У - 1 ^ 1 у I . Упорядочиваем слова из W ( u ) , 1А ( v ) по длинам: U, .. г и „ \ ... & V ^ , . Рассматриваем пары и , и, ; v , irt л для каждой из них Еыясняем справедливость - 5S -