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

кого типа. Рассмотрим конечное множество слов ■ •’ , где Vi- С г : i7* ) • и полугруппу , порожденную этим множеством. В дальнейшем запись &Jfv будет обозначать толь­ ко такие подполугруппы полугруппы &+ . ЛЗММА 2. Для любой &ЗГ-* существуют слова такие, что для любого j ~с ) ( < * ■ ) ) и ^ ) . ДОКАЗАТЕЛЬСТВО. Пусть . Выпишем слова ^ „ с л е ­ дующим образом: A-i , <* 3 .. .. - ■ ^рд- ■ , где для любого g (g-Gp) 'г,(< 4 )±** f и для любого g ^ pv jfcp i > Т’ Ц - ^ ' г Ц н О » vn. . И ДЛЯ ЛЮбОГО -J p t + i * p i + g i рд hv L "c (. 4 ч _ э toLpi + 0 ) фтз (t*p +0 1 . Пусть г * % (-^jv»») • Докажем, что 2 бМе({Д 1 , . . . Возможны2 случая : а ) Н е &+ •, б) ягф&-+ а) Для любого <А*ек*- ? г<*£. » где «А ^ е ^ « й * » , •D (Ык.) ^'ОС^к.О . так как &+ однородна. Следовательно, Н перв' водит все слова, длина которых меньше или равна *п. , в слова той же длины, т .е . | д 1 з переводится Z само в себя, но тогда I е Ng-C ^ cti.. .,*(>'^) ; ^ б) Представим KeG в виде 2 = a Ji,X , цг-О, * e (r" . ( I ) . Возьмем сАк.б^ЛГ» . Оно переводится 2 в некоторое cik' e ** . Используя ( I ) , имеем : <кк и e U X дк . Тем самым рассуждения свели к случаю а ) . 2 . Пусть i £ ^G- (.{<**, - -■ df \ ) . Докажем, что 2 е N&ff(nnw( -a**" »» ) Как и в предыдущем пункте, возможны два варианта: когда 2 е О''4' . и когда 2 ^ Q-"*" (случаи а и б соответственно). а) Пусть i e & r . Берем любой элемент е(^е **Л*-» , тогда <*4: ’ |ЬV1•- bi»* Умножим справа обе части равенства на 2 . A kt-’ Ь- ц - - - e>tD-i= b-ci 2 oUv- . где 'a(otiu-) -•» (bV oV ^ Продолжая этот процесс, имеем : cL *.2 = 2oUi ■■■■dixv- , т .е . г «% (* л ч д б ) 2 е& * . Доказательство в этом случае очевидно. Лемма доказана. Из этой леммы и результата 5 следует доказательство основной теоремы I . Замечание. Так как все <*-j е X » с , то элементы указанные в лемме I , мы можем эффективно выписать. Это множество назовем множеством, соответствующим , и будем обозначать <$* . Л й ММА 3. Существует алгоритм, который по всякой системе ви- , а <4-4 = •'ЗЗЬг 158