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

если она удовлетворяет либо условию К ( * / ) , либо конъюнкции ус­ ловий K f i i i Т (ч) ( либо К ( * ) &■ Т ( ь ' ) . Основная цель, данной статьи - доказательство следующих теорем, ТЕОРЕМА 1 . В любой конечно-определенной полугруппе о малым налеганием разрешима проблема непустоты пересечения двух конечно-порожденных подполугрупп; т . е . существует алгоритм, который по проиввольному конечному множеству слов , •• ■, , Ки определяет, существует ли элемент Р , входящий как в И, = < 1 * 1 , ■■■, > , так и в Йх - < К » •* -» К* > • ТЕОРЕМА 2 . В любой конечно-определенной полугруппе с малым налеганием разрешила проблема свободы конечно-порож­ денной подполугруппы; т . е . существует алгоритм, который по произвольному конечному множеству слов U ,', . . . , определяет, свободна ли подполугруппа И , порожденная этим множеством. Заметим, что теорему 1 можно доказать и для случая любого конечного числа подполугрупп. При доказательстве теорем исполь­ зуется метод типов [ 7 , 8 ] . . Рассмотрим сначала вопрос о том, какой вид могут иметь равные слова в полугруппе о малым налеганием (лемма 1 ) . Дока­ зательство лешы 1 проведем только для полугрупп с условием K ( i)% 7 так как случай к ( 4 ) уже рассмотрен в [А ] (см . так*е [ 2 ] ) , а случай К ( л ) Я Т (5) лишь немного технически слож­ нее i Следует отметить, что длинная формулировка леммы 1 стано­ вится прос Й я естественной , если польвоваться методом диаг­ рамм [3 J. ЛЕММА 1. Пусть П - полугруппа с малым налеганием в I I * V в П . Тогда верны следующие утверждения; 1 , Существует последовательность элементарных преобразований ot А- % V , целое число г г » о к слова ftX) S i , T t т а к Ц , •;то SK 'RK ; причем H i не затрагиваются элементарными преобразованиями; 2 . Для любого г существуют целое Число- к х > 4 , олова X q , Y ij . куски А ч > б </, Сй > таки е, что s{ * Ус< ... >, 77 * к , ... П>. причем для любых j ( / i J i k t ) 69