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

Если предадут™ выполнялось то в качестве <% выполняется аналогичное пре образ ование, описанное в ( ос^-) , с учетом ( о^ ,а) . ос6 . К последовательностям (5 0 ), (5 1 ), (52) применяем преобразование , переводящее их в упорядоченные ряды: (Д ,) * А ) « (50) % < У (510 <N/ А * 4 « . . . (52) Уч; тывая строение слова и г , с помощью которого осу- ществляется сокращение, можно убедиться, что ряды (4 0 ') - (520 удовлетворяют условиям Ц ) - ( З ) леммы П. Поэтому с помощью преобразовании Щ ^ преобразуем ряды ( 5 0 ') - ( 5 2 ') , в ряда, инвариантные относительно этих преобразований: С Д ) < (М { ) , . . . < ( Ж ) ' г * " (53) Y ' <; Y ' « 4 Y a If >2 • • • 9/ » (54) А 4 V ' • • • *=• ■ (55) d i . Н а р я д а (55) удалим те подгруппы Д , левое крыло которых КЛ(Ъ! ) не является начальным подело' тм левого крыла mi одного (Щ в ) г~да (53) либо начальным подоловом ни одного , (- = * < , где % - слово ряда (5 4 ). Д , У рядов (53) и (4 8 ), (54) и (49) выделяем общие мак- сямал- ые начальные подцепочки: А ) * ... * < А , ) P V /Л/ гч/ V 4 у ; . < Y / (56) (57) ° V Проведем следующие замены. Ряд (45*) заменим рядом ( 5 3 ), ряд (46") - рядом (5 4 ), ряд (47") - рядом (5 5 ), ряд (48) - рядом (5 6 ), ряд (49) - ря­ дом (5 7 ). схю> Выполняем преобразование ( Q 6 j ) . ' d it1. Если при осуществлении преобразования & v r нельзя - 55 - . С*.1