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

2 .2 . S - К у . надо д о к азать, что E t K i - Ку # t S f t * - * * = F < K t Х у R iT f , < . . . * « . Из определения типа и из леммы 1 следует 6 tj 3 Я a-i = Л ' / i f Еу Xif ■ -- X y _ E1 K, --. Yy ( 5 ) Кроме того, так как не затраги вается элементарными прео­ бразованиями, то R f . ' Rf . Tf.-^ . . . Я п . Из последних равен ств следует, что ( 5 ) выполняется. Таким образом, случай 2 полностью разобран. Мы снова по­ лучаем противоречие с минимальностью слова Р . Противоречия, полученные в обоих случаях, доказывают лемму. ЛЕММА 3 . В любой конечно-определенной полугруппе с малым налеганием разрешима проблема вхождения в конечно-поро- кденную подполугруппу. ДОКАЗАТЕЛЬСТВО легко вытекает из следствия I. Теорема 1 немедленно еле,дует из лемм 2 ,3 . Для доказательства теоремы 2 нам понадобится еще л еш а 4, утверждающая, что равенство в полугруппе с малым налеганием "не слишком сильно отличается" от р авен ства в свободной полу­ группе (точная формулировка дана ниже). Рассмотрим равенство Е F f - Е F a в полугруппе П- с малым налеганием. По лемме 1 можно запи сать: E F 4 = Яо S, Я , 4 Я*. , Е Fz R o T y /Z , . . . 7 1 Я * . ЛЕММА 4 . Пусть Е F, - Е F t . Тогда для любых F d . (в) (7 ) ( fit ( х * ) мпкет быть пустым только для полугрупп из к л асса К М Л Т ( s ) . из того, что Е = t , S r Я f * * * Я<-у Хс Е п , ! Е пП следует^ что Я о s f * , ■ . . а £ . , - Я о 'Ey Я , - и либо ХЧ — * ъ у . ■ У — • ■ ^ 4 -1 r v ) либо А Ъ - - К / К - * я - < X ij s } где Yy 2 •* ; к - , X = х А > - \ Х у , причем слово Ус у 77