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

ЛЕММА 3. Пусть VV - элемент из 0 t o и nt- - нату­ ральное чиоло. Существует только конечное чиоло элементов полу­ группы СХ0 • которые равны W в Ot и имеют длину < mL . Кроме того, существует алгоритм их нахождения. ДОКАЗАТЕЛЬСТВО , Будем доказывать лемму индукцией по дли­ не элемента W . При d ( w ) - 1 лемма очевидна. Пусть д ( № ) - п и и / г д и ' ' , где рядом с нет слога из той же полугруппы, что и О- , Предположим по ин­ дукции, что существует конечное число элементов, которые равны W в Ol I имеют длину £=пгL и существует алгоритм их нахождения. Множество элементов, равных W ' в OL, обозначим через М = = Рассмотрим ряд равенств вида w -о. и / г , w=aWz, . . . , w =аЩ, . . , , w-aw^.. Для каждого элемента о.WL о дополнительным определяющим словом С; = а к i v * . г д е а ~ а на * , w£ = w LHw i K , отроим дерево элементарных преобразований. Для этого, заменяя d на равные ему в Ot элементы, получим [ а * г г \ л / ; к W = a io Kw lMv v *=-1 : (7) l a ' / g e i v ^ K , где CL* w ? = г л в o t Элемент в общем виде можно представить так: gt - Г <9) / 0) v Г (г> / ,1> и > . ГО л ХА Л, •"<»/>* ••• Хл, ... xt clt_■ Покажем, что на границе Q-H и ? д нет дополнительного оп­ ределяющего слова. Допустим противное. Пуоть с * - а " г * е J , , а * * а * ъ " ' 98