АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

\Л\< 7лmm (\А| ,\ц). Легко видеть, что К/ С V п К д . Из включения К?, с \ч2 имеем \С с Kg . Из включения К 'с К получаем С л е д с т в и е 2 . Пусть VI - полугруппы И” из класса К , и в ется порожденное тождество. Тогда VI тивную полугруппу натуральных чисел. Т е о р е м а 3 . Цусть U - V в полугруппе И ’ t : K .i . Тогда существуют натуральное число 11 , последовательность элементарных преобразований от Ц до V и слова k { , o i . , l i такие, что Ц ' Rc i V,R a . .. onR -,1., \ ; R0T , - T - u , последовательность не затрагивает слова R,| ни для одного индекса -I , и для любого t (_ i < i С п ) существуют натуральное число щ » сло.ва и куски At,) , ¥>tj , C\,\ , И - J -- ТЧ ) такие, что Ъ\ ’ X-j 1X i g ..Д к н , T t Yt.| V i 2 ... Y i t i v , A i a X i.) t’>, Vv . ,0\л - определяющие соотн о­ шения, слова A v i , l , . | , 3 i r n Д Ч 1 Ц - пустые и для любых Д i , ‘. fi -, ТЦ ) ровно один из кусков Ъ',,А . A i () и - пустой и ровно один из кус­ ков D ; ;l , 1 Ч () и - пустой. Д о к а з а т е л ь с т в о . Мы приюним индукцию по числу к элементарных преобразований в последователь­ ности от U до V . Если к О , то лемма очевидна. Предположим^ что, лемма верна для некоторо­ го к и что ( к н ) -о е элементарное преобразование заменяет t i на V , где V: = V - определяю­ щее соотношение в полугруппе 1Т подполугруппа А юполня- вложима в адди- - 14 -