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

Рида O S ) , удовлетворяющего условию ( I ) леммы Л, п о том у слово X X X обладает либо свойством ( и ) , либо ( sh ) , либо (je d t). Таким образом, применяя преобразования •$, , «#г , , мк через конечное число-патов яреобрат/ем ряды (2 7 )-(2 9 ) в ряды (3 0 )-(2 2 ). 5. ТЕОРЕМА 4, ^Пусть #/>№■},&) - конечно порожденна подгруппа группы G и пусть W - произвольное слово группы G* t ' W t i y p f M o ' S ) , Существ,, ет алгоритм, преобразующий подгруппу \W,gp(JUo,Sy> в подгруппу y>(JU i, S J) , где < Ч д р ( Л 1 о ,& » = 9 р Щ > ^ ДОКАЗАТЕЛЬСТВО, .тусть основание S подгруппы yp(Jltc,S) порождено подгруппами ряда С4о; Множество М0 содержит нетрансформы, которые мы упорядочи­ ваем по длинам: Построгал для рядов (4 5 ), (46) вспомогательный ряд (46) А ХА ^ ■44 ' (47) Если W является транцформой w = t e B, t \ , . Д t t s K t 6aB^ . . . В ? Г £' б / ' Г * x ~o, 1 1 , то пополняем ряд 4 5 ) циклической подгруппой < W > . При этом возможны два случая. 1) Среди подгрупп ряда (45) содержится подгруппа: Щ ) t \ ,. Bs f r A c j С ‘% [ .. в / г а г которую ваменяем лодд’руппой ~ (W ) . 2) Среди подгрупп ря,та (45) нет подгруппы Щ м “ й ,л .., в,, г£% ’ .,&;ч •* ТЗгда подгруппу (W ) располагаем среди одгрупп - 50 - )