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

ДОКАЗАТЕЛЬСТВО. Пусть п, * г\а . Тогда .( а *ШПп’~ А*тЩ , (л"УХ )П^ = д 2™1- W, . Отсюм (лг*Х )п,= ( л ^ Х ) п* , то есть A^ n , j n l=A ^ n aj n 2 Если у >0 ,т о получается противоречие с однородностью полугруппы. Если , т - № - * > = ( ] [ ) * - * • а так как X - неприводимое слово, то но лемме 5 Х У 1 ' не содер­ жит , Полученное противоречие доказывает лемму. Рассмотрим решение уравнения ( 3 ' ) , не являющееся дельта сопряженно периодическим. Составляем множество неприводимых не дельта сопряженно периодических слов длины не превосходящей 2miMt,>m°+2m„ ,гд е JM - наименьшее фиксированное неотрицательное целое число такое, что длина представления основы любого Wt €(w(W) будет не превосходить 2гг\от° +2 т а Если длина основы X меньше 2т™° + 2т 0 , то из оп­ ределения дельта сопряженно периодического слова следует, что З к еХ1 ,Т еС г+ такие, что Т Х ^ - Х ^ Т , где X * -непри- водимое слово, длина основы X " не мангле 2 m " la +>v0 и X * является решением одного из уравнений вида u2kt,y * \ n А2т г / и / * (Л* Л ) =А Wi г (9) где ТW ^ V V ' T. Теперь молило установить,' существует ли п такое, что основа слова (X" *)п равна основе олова Wt для некоторого i . Если это не та к , то для данного X решение (Аг*Х, п ) не оущеот пует. Пу~ть такое п.0 имеется. Тогда для соответст­ вующего уравнения ( 3 ' ) , если оно имеет решение п, при данном X , а, = п 0 . Таким образом, ^остается найти . Для этого запишем нормальные формы Х * а" =&<*V . , W* = a ^ V . По теореме Гарсайда из (9) получаем диафантово уравнение: 2 к н у п 0 + О! ~ 2 kt<rrii +(i , Решая это уравнение, устанавливаем, существует ли решение уравнения (3) для выбранного X , Аналогична} решению_урав- нений (9) рассматривается случаи, когда длина основы X будет не меньше 2т™°+_2гп0 , ОТУЧАЙ 3. X - дельта сопряженно периодическое слово, ОПРЕДЕЛЕНИЕ. Слово W из полугруппы &* будем называть - 77 -