АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

частью которого оно является. Поэтому S ^ m определим как максимальное общее начало определяющего слова, оканчиваю­ щегося на и определяющих сл ов, оканчивающихся на Аг 2 • .. Таким образом, в силу однозначности определения At и S t , имеем однозначность определения b t словом А . Лем­ ма 12 доказана. Замену в слове А Я -приведенного подслова В на О назовем обобщенным Я-привэдением слова А , если шполнены следующие условия: 1. 3 s Ba* . . Вт . С~С1С' > . . .Ст» где b i S t C t S t - i <£ R , i = 1 , 2 , . . . , т , S 0= S m = I ; 2 . |В| > 101. | Ъл\ . . . В - iUIC^ . . . C i S i l , i = I , . . . , т - I , | В i 'Ь — 2, •.., ГП , 3 . Если А^=А^ЬАг» то общий конец и ц и общее начало А 2 и О т пусты. По аналогии с R -приведением будем Б называть заме­ няемой частью, а С - замещающей частью и употреблять по­ нятия обобщенно Я-приводимого и обобщенно R -приведен­ ного слова. Л е м м а 13. Если А - R -приведено и D получено из А в результате обобщенного R -приведения, то - с в о ­ бодно приведено и к В не применимо сильное Я -приведение. ° Д о к а з а т е л ь с т в о . Пусть А=А*ВлЗг...ВтА2 к X > = A a C’4P 2 . . . Cm А2 . Тогда . . . Cm - неприводи­ мо и, следовательно, в силу условия максимальности обобщен­ ного Я -приведения, слово Б - свободно приведено, а Я - приведение слова Т) может произойти тоЙЙйо с захватом кон­ ца и начала С/\ или конца С'т и начала Аг. , так как захват Р< или C m , в силу 0* > 1 /4 R и C m > l / 4 f t , приво­ дит к невозможной свободной приводимости слова А' . Поэтому Я -приведение может захватывать только начало Сц или конец р т , которые шныпз 1 /4 R , и, соответственн о, конец А1 и начало А т , которые мэнылз 1 / 2 Я , то есть R -приведение не может быть сильным. . ( - г-п -