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

УДК 5 1 2 .5 3 2 Ю.Э.ТРУБИЦЫН Тульский пединститут ПЕРЕСЕЧЕНИЕ ПОДПОЛУГРУПП В ПОЛУГРУППАХ С МАЛЫМ НАЛЕГАНИЕМ Данная статья посвящена исследованию некоторых алгоритми­ ческих вопросов для полугрупп, заданных копредставлением с ус­ ловиями малого налегания определяющих слов. Ранее полугруппы с различными условиями малого налегания изучались, например, в [ l - 5 j . Мы будем использовать следующие обозначения: |Х I - длина слова X ! 2 ' - равенство в свободной полугруппе; = равен ство в рассматриваемой полугруппе; А - пустое олово. Дадим необходимые определения. Пусть полугруппа Г! зада­ на конечным копредставлением: п - - < * * ; 4 * 4 ( ч I > ■ Б ез ограничения общности можно счи тать, что множество опреде­ ляющих соотношений 1 ) не содержит тривиальных соотношений вида А - А ; 2) симметризовано, т .е . если А = В - определяющее соотношение, то и В = А - определяющее соотношение и ие того, что А ~ В , В - С - определяющие соотношения и А $ С j сле­ дует , что А ~ £ - тоже определяющее соотношение. Обоеначим через М п множество все х определяющих слов полугруппы П . ОПРЕДЕЛЕНИЕ I . Если X , Y е М„ P Q f i , Y = S 6 7~ , где Р Ф S или Я 2 Т , то слово 6 навиваете* куском. Пусть р , f - некоторые натуральные числа. ОПРЕДЕЛЕНИЕ 2. ' Полугруппа И удовлетворяет у» ловию К ( р ) , если ни одно определяющее олово не разлагается • произведение менее, чем Р ку сков. ОПРЕДЕЛЕНИЕ 3. Полугруппа П удовлетворяет р ловию T f f ) , если из условий 1) слова и<> • - » непус ты; 2) Х Н , 2 < Y , P P / Z s G - определяющие слова; 3) - Zj Ц , 4 - Р(ч~ Pi. Pi - определяющие соотношения ( j ж 21 ■■•» ^ >■ i ~ z., . 1 1 ) f 4) з * $ * * < ; сл ед у ет, что ХН 1 = Р н ( } Z 1 Y ^ Z C Q ■ Будем говорить, что П - полугруппа с малым налеганием, 68