Алгоритмические проблемы теории групп и полугрупп. 1994 г.

Обозначим через [%} множество всех таких диаграмм. Раоомотрим последовательность: (*> Щ ^ , , •., > Нт 1 П1> где Н( - куски, У^‘ , 0 < ^ т , 11Щ11~-/1Щ0Ц} и Н^1 ^ ОПИУШШБ 8 1 . Последовательность Отбудем называть вазовой, если о,уществует опецпыльная $ - диаграмма $ ие {М ] , для которой олова \Л >0 , о граничными циклами а , , ) ( И//« являютоя метками граничных циклов $ 5 ' здеоь для каждого 0 < И т , в / еоть циклическая перестановка граничного цикла Ц' кольце­ вой подпрограммы диагршлмы ¥ 0 , либо гранич­ ного цикла % , а Н { т<^С^^) , ( ¿ * М 0 , и слово Н1 . . . Ит - метка пути ? * € , , , . £/*, , соединяющего начальную вершину 0 * 6 1 диаграммы о вершиной О Базовую последовательнооть Ш будем навывать фундамен­ тальной, еоли О * / ^ ^ ^ и 3 &г О Ч 1 Г < т , Так как число куоков конечно и число слов слоговой длины II кУ,|| токе конечно, то число фундаментальных после­ довательностей конечно. С каждой фундаментальной последова­ тельностью ( * ) овяэыааем олово и « И4Н ^ . .. Нт Н ^ , . . И'/. Очевидно, и в (№о ) , Л ?№»)- нормализатор слова У/0 в О-. Покакем, что множество ( и ) порождает Л ^ С щ ). Пусть М - свободно приведенное слово , принадлежащее то е с т ь Я V # 2 *И/0 . Пусть 1Я1>{. Рассмотрим приведенную /? - диаграмму М 0 о граничными цик­ лами с . , Г, с И ^0 , ^С Т с)* W i J coo тве тствуицую оо - пряженнрсти тогда 6 { Н }. В М 0 оодеркитоя некоторый путь $ , соединяющий началь­ ную вершину Ое<>с с начальной вершиной такой , что ^ ^ * 2 . Пусть также М0 - с - П - алойная Ц - диаграмма и . где ^ _ путь, гометовиьй и М 0 г е * - 49