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

Слова - из (10) известны. Наша зад ача - найти олова Ua>(f)...U(lh , ) ^ i ( i = i ^ ) , удовлетворяющие соотношениям ( 1 0 ). Согласно л еш е 7 L(и м>(1 ).. ■ U (jy)( l* )) ^ L 0 -tdb~K 'f t(u(l,(1)... u(i)(Xi))4 2 t0+& ~fC (ШО . В каждой подгруппе Hi составим множество всевозм^ дшх слов & L>(u(Q(l)).. .<Pa Y u °C l L) ), прообразы которых удовлетворяют усло­ вию: l ( u u ,0 )...U (l)C ti))<K (или K ', i * v ) . Этих слов (образов) существует конечное множество нр , так как прообраз может быть записан в виде Lir . M k**(%iy,2i ) . . то подгруп­ п е, порожденной ядрами. AjU> п (rL‘ i>2), в образе соответствует лишь один олилент ц р о ; это ликвидирует бесконечность мно­ жества ядер , а число элементов ~г< , у£ конечно для слов ограниченной д амы . Из всех множеств Нф выберем по одному произвольному слову и рассмотрим его произведение на соответствующий ^ : В первых •№-( строках возможны сокращения между ^ и f V 4 n > ...) . Рассмотрим первую строчку. . Пусть в ^ в сокращение вступает конечное подслсво Ф ^ ялчнп / , . И ПрООб^ХЮ WlViO -J f f U up,П'ЛЛ n '£UMA<J у, Ф Р Ш Ф - Ф Ч и 'Ш . .Ф Ч и Р о ,)) - Если у слогом - И З -