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

^cC^ . Случай I . Слово R -приведено, В этом случае R -приведение слова ( 2 ) , есчи оно воз­ можно, должно бьшо бы захватить конец и начало Hi , что невозможно по лемме 5. Поэтоцу слово ( 2 ) - R -приведено. Случай 2 , Слово к0Сц не является R -приведенным. Рассмотрим возможности R -приведения в зависимости от затрагивания или захватывания слова . Случай 2 .1 . ft -приведение слова А0СЛ захватывает не все Ci . Поэтому f t -приведение захватит начало C i , ко­ торое i 1 /4 ft, согласно лемме 4 . Обозначив через й\ ко­ нец С< , незатронутый ft-приведением, и притеняя к слову АоС* последовательно ft -приведения справа, налево пока это возможно, из слова (2 ) получим слово (3) Ak Ek * где m ? I , ft > I . Согласно лемге 6 слово А к Е к Е к ^ -'Е г Е ^ * ft - приведено. Так как также ft -при - ведено, то R -приведение слова ( 3 ) захватило бы Оц . з а ­ тронуло бы и Н<( , что невозможно по лемге 5 . Поэтому слово ( 3 ) ft-приведено. Случай 2 .2 . f t -приведение АсС„ захватывает все Сц . Так как по лемге 5 R -приведение не затрагивает , то вернемся к слову А0Сс Е>с и проведем с ним ряд f t -при­ ведений в другом порядке: АХ сВ с - A c G iG j b c ~ — AoC ^CgBc.Bi — AcCsJ??bi -A i.A ^gi.QB i A ^ Q b i , где S > 1 / 4 R*, q > 1 /4 ft. Рассмотрим два случая в зависимости от возможности ft -приведения слова BG) • Случай 2 .2 .1 . Слово SG) R -приведено. Проведя последовательно ft.-приведения слова A^S спра­ ва налево, a QB1 - слева направо, получим слово ( 4 ) Ak .Sk ... EgS'C? Иг ...Ипг|Ь|т\ , где S ' - конец S , Q' - начало Q , S '# I , G?'# I . По лемге 6 слова A k E k ^ E g S * и G)'Hg . . . Нт Ьгп R -приведены, S'Q также R -приведено, кал часть R -при-