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

является максимальным отрезком в подслове Тогда будем называть представлением В Пусть слово В имеет представление . Сдвигом в ' называется такое с л о б о С , что 1) в случае со = / или co = Z С=В , 2) в случае со> з С = Ht ,. Сдвиг В обозначается 3 “ t Слово в .называется приводимым, если, произведя несколько его сдвигов, получим слово, содержащее А 2 • В противном слу­ чае В называется неприводимым. Из определения сдвига следует, что д (& ) - &С&) , Так как множество слов равно!) длины конечно, то приводимость слова алго­ ритмически распознаваема. j Следующие две лаяла доказаны в работе [ 2 ] Л в м м а I . Пусть 2) п А - слова. ... нл А', - пред­ ставление % , 2>/?г , где т и /г ' - натуральные чис­ л а . ‘Тогда существует слово А)* , такое, что НЛЫ, А = и ( * ) ” = А 2/ 1А * Л е м м а 2. Если слово 2> неприводимо, то A)m не со­ держит А 2/71 По данной системе ( I ) можно построить конечное множество систем уравнений, решения которых будут сопряжены решениям систе­ мы уравнений ( I ) . Это множество обозначим ССО Определение множества.. СС / ) . В работе f l j показано, что всякую косу Gr можно представить в вдце A 2S R , где S натуральное число, /? - некоторое олово. Запишем косы из пра- i вой части системы Cl) в этом виде. <$у ~ Л JS‘A , С t где - слова. Система уравнений f ■*' ’=А 'В, I - А кЕ>^ г СВ,„..,3/, - слова \ пршадлежит С СО существует слово % такое, что с = К к . Легко видеть, что ё>СА1 ) ^ Э С А - ) . Следо­ вательно, в ССО содержится конечное число систем. Так как проб­ лема сопряжешюсти в группе кос разрешима, то шожество С СО ал­ горитмически строится по систоле ( I ) . Л с м м а 3. Пусть £0 - решение системы C l). Тогда сущост- вуот коса <?0 - решение некоторой системы из С ( 0 , такая,что Q0 - A 3 tO . где О - неприводимое слово и Ra сопряжено Qd г - L19- - п