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

I . Если цодслово ( tdLi, г, t? ) ' является изолиро­ ванной закрытой левой половиной нетрансформы нечетной длины: то в этом случае слово и г' заменяем словом urt f для которого строим граф Г w n , 2 . Если является изолированной закры­ той левой половиной нетрансформы Щ четной длины, то длину w ' можно укоротить. O l3 . Пусть ни O l, , ни 0^2 нельзя применить. Тогда про­ веряем справедливость равенства: В ( 22 ) где k ^ U , , если , и U-, , если £U l =,1 { tyLt, - слог олова git, t , нумерующего множество Если соотношение (22) не выполняется ни для одного из возможных tyi-ц , то ы 4 д р ( М 0г S). Таким образом, применяя преобразования O tL , мы можем через конечное число шагов установить, принадлежит и г под­ группе 9 p (M 0,S) или нет. Пусть в слове иг р - О , , если 6, = - f , и б, 4 U4 , если i = ( . Тогда, если А а - непустое поданожеотво, то вместо 01 ,, ( выполняем следующие преобразования. Устанавливаем выполнимость соотношения: (23) где W e ( i4 i,) = /40i, , k e U, , воли £ ,= -1 , и k c U , , если <5, = t . Если озо справедливо, то длину tv- укорачиваем. В остальном следуем указанной выше схеме. 4 . Пусть W - произвольное слово группы G* и W 4 gp(JU0,S), Поставим вадачу: построить ив подгруппы урШо,S) и слова W нпвую подгруппу др(М '0 , S ' ) , где (W,дрШо,$))=#>М , 4), порождающие подгруппы которой обладают свойствами (а^ - ( а*.). Введем некоторые понятия, которые в дальнейшем будут играть важную роль. - 39 -