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

где ы = 0 , * 1 ; р = 0 ,± / ; £ , = *f =/ГЗ ; $ ' = ± / . h e Ut , если 8 S~ <, и h * U f , если 6 s ~ - f. Под длиной сл о т. будем пошмать длину несократимого, равного ему слова . Под дайной слова (3) будем понимать число L ( $ ) = 2 S +( , под длиной слова (4) - число L ty )= 2 3 . Представление слова груши G в несократимом виде в форме (3) или (4) будем называть каноническим представлением. ВM°Be д*V%t% ft... ft"B,ft .. ftbkHft, где <x= 0 , t f , &(= i f , Ul,7< y о^резок^ назовем начальным открытым отрезком, a t В .В1... t 6’ - начальным закрытым отрезком. Аналогичные понятия вводятся для конечных отрезков ЛЕША. НОВИКОМ П.С. Пусть слово X группы G , содер­ жащее правильную проходную букву t , равно единице в груп­ пе G* : Х= / . Тогда либо X ^ Y t t t Z , где Сб Ut , либо X * Y t c V ' Z , где С с Ц , . Знак и обозначает графическое равенство. Используя лемму Новикова, можно показать справедливость следующих утверждений. ЛЕММА I . Для каждого слова tir= t > где ot= 0 ,± f; ft=Ot ± { ;£<• = * / ; i= , группы G * сущест­ вует единственное каноническое представление. УТВЕРЖДЕНИЕ I . Из разрешимости проблемы тождества слов в группе & и разрешимости проблемы вхождения в подгруппы и , , и , следует разрешимость проблемы тождества слов в Группе ( г * . д г „ , ка\Ч Слова вида ( 3 ) , у которых t L y U . X t y U X U Z y .U f y U ) , назовем трансформами. Слова вида ( 3 ) , не являющиеся транофор- мами, а также слова вида (4) назовем нетрансформами, причем нетраноформы типа (3) - нетрансформами нечетной длины, а (4 ' - нетрансформами четной длины. У сл. в. вида (3) дллны 2 s +{ начальный (конечный) от­ резок t*L ,9 f t , . l S9 f t \'teh s p . ,. f t l y f t ) назовем закрытой левой (правой) половиной, отрезок tZ i^ ft... ty ftK g Р) - вскрытым большим начальным (конечным) отрезком. У слова вида (4) дайны 2 S начальный (конечный) отрезок t Llg ti,„, L.Sg l Z ^t-sg f t 4 . . . f t l y f t ) назовем закрытой левой - 22 -