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

2. Обобщенная проблема степенной сопряженности в классе групп с ус­ ловием С(5)&Т(4). Будем говорить, что группа G = (X; R) с условием С(4)&Т(4) удовлетво­ ряет условию Рк, если всякое разбиение любого определяющего отношения на минимальное число кусков содержит только куски длины к. Основными результатами данной статьи являются следующие теоремы: Теорема 1. Пусть М - приведённая кольцевая диаграмма сопряженности циклически R,R- несократимых слов w2", v_2m. дМ-сгит, <р(ст) = w2n, ср(т) _у- 2 т рогда если в м есть область D: i(D) = 2, то существует константа С, за­ висящая только от длин слов w, v и от длин определяющих соотношений в симметризованном множестве R, удовлетворяющем условиям С(4)&Т(4)&Рк, такая, что я, m <С. Теорема 2. В группах с условием С(5)&Т(4) алгоритмически разрешима обобщенная проблема сопряженности слов. §1. Введение Считаем понятие й-диаграммы, карты, кольцевой диаграммы, куска, симметризованного множества, деновской области, полосы известными. Для любого слова w символом w* будем обозначать одну из его цикличе­ ских перестановок. Слово w называется циклически приведённым, если любая его циклическая перестановка w* несократима в свободной группе F=F(X). Обозначим через |и| длину слова и, через ||и|| - минимальное число кусков, на которое можно разбить слово и, символы =, ~ обозначают графическое равенст­ во и сопряженность слов в группе G, |Щ - число областей в диаграмме М. Гра- ница карты М, области D - сМ, cD. Метка области читается по часовой стрелке, а метка й-диаграммы против часовой стрелки. Функцию метки обозначим через <р. Через /(D) обозначим число внутренних ребер области D в диаграмме М. Будем говорить, что в слове v есть й-сокращение, если существует гей такое, что 1 ) либо v е Viv 2 v3, г = v j 1 г2, || г2|| =1 и в словах V|r2, r 2 v 3 нет свободных сокращений и й-сокращение состоит в замене слова v словом vir 2 v3; 2 ) либо v = V|V 2 v3, г = v 2, слово viv3, возможно, сократимо в F=F(X), и тогда й-сокращение состоит в замене слова v словом vtv 3 с последующей заменой последнего рав­ ным несократимым в F словом [4]. Определение 1 [1]. В слове v есть й -сокращение, если существуют слова г\, г2, . Л £ R такие, что v = v 0 Vi. . . v*+t, г, в r'r^rf , || г} || >2 (»=!,*), = r 'r /r jr ;, Hrjll > 1 (, - 2 , ----- k-l), r,3= r l rjW /+l (/ - 2 , . .. , к- 1 ), \\r!\\ = 1 , ||r/|| = 1,(0 1 ) и в словах v0r 2, rk vk4, r,Jr 3 ...rk нет свободных сокращений и й-сокращение состоит в замене слова v равным ему в группе G словом v„rlV 3 ...r 3 v*|. Если в любой циклической перестановке и* слова и нет й, R -сокращений, то слово и называется й, й -несократимым. 121