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

дельта слоном, если существует р е такое, что Wp= A k , где к - четно. Очевидны следующие леммы. ЛЕША 9. Если хотя бы одно из слов множества (Ч (W) является дельта словом, то и все слова множества |и(И/) явля­ ются дельта словами. ЛЕММА 10. Олово Ха , входящее в решение , п0) одного из уравнешШ ( 3 ') , является дельта словом тогда и толь­ ко тогд а, когда IV, - дельта слово. Следующие две леммы доказаны в работе [5]. ЛЕША I I . _ Пусть при некотором п справедливо соотноше­ ние д 2У» п&*щ = ws n и пусть W ^ T - T M * , T 'WfT =Al W,* , где tV,*eG + ц W * не содер­ жит л , L 6 / . Тогда для данного п имеет место равенство &s*°n +k ' l w * = W ) n . ЛЕММА 12. Пусть W - дельта сопряженно периодическое слово. Тогда существуют 1} к *У 1 , Те G* такие, что ТМ£г Тч , где R - четное и Wi =7, WST i Т, положительное и Щ Л&1 , a Hif - минимапь- ная основа слова И/5' . Будем искать решения каждого уравне­ ния ( 3 ' ) , считая X дельта сопряженно периодическим словом. Возможны подслучаи: а) у >0 . Приведем каждое_из слов Л?т< к норг. 1 альной форме А*"4 IV, = А W , где W ? л . Тогда из соотноше­ ний А*УпХ п =А*' W i имеем следующие условия: . Так как п >0 , то // ^ а ‘ & • (Ю) Составим множество пар К = { ( ^ , п ) } , удовлетворяющих условию (1 и ). Затем составляем множество & всех непр1води­ мых, дельта сопряженно периодических слов, основа разложения которых будет меньше 2m™^+2rn0 и не являющихся дельта сло­ вами. Для каждого слова Х а из & и пары ( у а п 0 ) е К сос­ тавляем набор { а ^°Х0гп0) и проверяем, является ли этот набор решением хотя бы одного из уравнений ( 3 ) . Таким образом,через конечное число шагов определяем, будет ли хотя бы один из - 78 -