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

д а Ы 9,4 В.Н.БЕЗВЕРШЙ Тульский пединститут РЕШЕНИЕ ПРОБЛЕМЫ СОПРЯЖЕННОСТИ ЦЯОВ В ОДНОМ КЛАССЕ ГРИШ Рассмотрим группу < *= < й * Fc ■ Uy = Yd i (Uy), t « Л , «/‘ 4 > , a являющуюся древесным произведением свободных групп ^i ооотве от­ веяно рангов П; с системой свободных образующих *,у, Л объединенных по изолированным подгруппам t {, , • гда • с помощыо фиксированных изоморфизмов {Sg j , причем каждая объединяемая подгруппа Уд < F t имеет вид Ц д * , f y ( X n , *(*>■• > * < * ) > , здесь m < n i , СЛОВО f y 4 < X irn > , P is Ы , **& * Г П . ОПРЕДЕЛЕНИЕ. Будем говорить, что в группе В разрешима проблема степенной сопряженности слов, если существует алгоритм, позволяющий установить истинность или ложность в в следующей формулы п . 1* = и г к )). З г ( V • m ,ke{Z \ lO }} TEOFEMA I . В группе & = < r i * F i ;U ^ = Vjt (Uy ) j i e J ( j Л разрешима проблема сопряженности слов, ТЕОРЕМА 2 . В группе <2= < П*Ff 5 Цд = разрешима проблема степенной сопряженности слов. Предварительно докажем теорему 3 . ТЕОРЕМА 3 . Пусть F - < a u Qi> ,£?„> - свободна* групп*, Ctu. . a n её свободные образующие, и пусть f ( o Ul i a n ) > - подгруппа F , где к < п я слою f а п ) йе принвдлежят подгруппе группы F . Тогда, если для некоторого z e F имеем Н гН Ф Н t ter z ' F ifiH ‘ <V>t t r t p , где < v > - возможно единичная подгруппа F , ЛЕММА I . Если для некоторых слов У , Y из F имеет место равенство XY=YX~\ г а X s f в F . Доказательство проводится методом математической индукции пс длине У , ДАМА 2 . t l ] . Пусть в свободной группе F слова X , У удов­ летворяют соотношению X Y *Y X . Тогда У ш Y содержатся в одной циклической подгруппе группы F .