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

w « г , м с - а 1 Очевидна следующая Пусть пара ( Х 0 , п а ) - решение уравнения (2) Тогда уравнение Х п = Х*&* разрешимо ЛЕММА 2. и W T = T W * в а . Дальше считаем, что \M * e i ^ iW ) , Представим X в виде X -AixX, , где -х е Z , X , «&' . ОПРЕДЕЛЕНИЕ [ I ]. Пусть Н, - представление слова В . Сдвигом 5 называется слово С та ко е , что: I . В случае ш - 1 или их=2 С=В, 2 . В случае u s z i С=Н2 Н,НШ....Н3 . Сдвиг слова Ь обозначь».! Й . Для всякого слова 5 могло выписать последовательность слов 5 » SG такую, что 5,- = 3 (_, для всех t = 1 ,2 ,... ,к, -- . Из определения сдвига сл еду ет, что все сло­ ва в указанной последовательности имеют одну и ту же длину. Так как Сг+ - однородная полугруппа, то существует такое J<0 - натуральное число, что слова 5 0 , ^ р а з л и ч н ы и S ko = S j , где 0 « / < к0 . Слово S будем называть лриво- 'Димым, если в указанной последовательности найдется слово, содержащее А г . В противном случае S называется непрйво- димш . ЛЕША 3 . Пусть (Х ,А**У =И/Ла,п ( 3 ) , где X, Тогда существует слов W сопряженное W в Сг такое, что ( % a * * r = w * A * m (4) ДОКАЗАТЕЛЬСТВО. Пусть представление слова X, имеет вад . Л еш а тривиальна, если £ « 2 или слово X , содержит А . Будем считать, что t » ' 3 . И з равенст­ ва ( 3 ) : XW =WX, . (5) Действительно, из (3 ) ( Х 1Аг х ) =АгтХ , / хШ гхуX / . (6) Сравнивая (3) и (6) получаем равенство (5) в группе £ . Так как X ,, IV -пол лителыше слова, то по теореме Гароайда X, W = W X , . Обозначим Q — Hfe Hj., . По лемме 8 [4] ив равенств (5) сл едует, ч .о существует такое слово X * ,что OtV = W*Q . Из равенства (3) имеем: (X ,ASx) n - - НД Hi, A im X - A Hj2 H jt W . так как - 74 -