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

•рренному в Лемме 2 . Мы опять пришли К противоречию с минима­ льностью равен ства ( 1 1 ) . Следовательно, случай 2 толе невозможен, поэтому длина . каждой ив частей минимального нетривиального соотношения не превосходит числа ( К . Таким образом, Чтобы проверить, сво ­ бодна ли Н , нам надо выяснить, существуют ли нетривиальные соотношения между элементами ее неприводимого множества по­ рождающих, причем достаточно рассмотреть только те соотноше- квя, левая и правая части которых имеют длину не более К . Сто, очевидно, можно сд ел ать, перебрав конечное множество со­ отношений. При этом используется разрешимость проблемы равен­ ства в рассматриваемых полугруппах. Теорема 2 Доказана. Рассмотрю/! теперь проблему сопряженности слов в полугру­ ппах с малым налеганием. В ста ть е f lO ] вводится понятие соп - ряжекнооти первого и второго рода. Как следует из [ И ] , в полугруппах к л а сс а К ( 4 ) разрешима проблема сопряженности второго рода. Нас же интересует проблема сопряженности перво­ го рода. ОПРЕДЕЛЕНИЕ 4 . С -преобразованиями полугруппы П называются элементарные преобразования слов из П , а также перехода от слова вида й,- * к слову к й/ и обрат­ но} - произвольная буква» К - произвольное слово. Слова К й V сопряжены в первом роде ( i t ^ V ) , если существует последовательность С -преобразований, пере­ водящая U' в V . 3 . В любой конечно-определенной п пе с малым налеганием разрешима проблема сопряженности перво-' го рода} Т .е . существует алгоритм, который по произвольным двум словам определяет, сопряжены ли они в первом роде. Заметим, что понятие сопряженности первого рода можно описать с помощью кольцевых диаграмм (применение кольцевых диаграмм к группам изложено, например, в [ 9 ] ) . Сформулируем аналог леммы 1 для сопряженных сло в. ЛЕММА 6 . Пусть П - полугруппа с малым налеганием и U ~ V _ в _ П . Тогда существуют такие циклические пере­ становки & > слов ^ соответственн о, что либо 1 . (Z - V в полугруппе П : либо