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

УЖ SI9.4 . А.Е.Уотяи (Тульский пединститут) К ПРОБЛЕМЕ ЛЕВОЙ ДЕЛИМОСТИ ДЛЯ . И0НЕНН0-0ПРЕЩВШЗШХ ПОЛУГРУПП КЛАССА Впервые полугруппу с неразрешимой проблемой делимости постро­ ил А.А.Мврвов [ 3 ] . С.И.Адян j l ] доказал, что для полугрупп о совращением проблема делимости таяже неразрешима. Для полугрупп Из влаооа, приведенного в работе [2Д , положительное решение проблемы делимости получила В.И.Гршшшнгер. В работе [4 ] приведено определение класса полугрупп К и до­ везена теорема о том, что существует алгоритм, позволяющий узнать для любых слов W и V в полугруппе, принадлежащей влассу К , равны они или нет в П . Пусть полугруппа |~1 , заданная образующими Qt , GjL, и определяющими соотношениями , Оц \ (I) = C U M , • • ■, ^ ) , (2) принадлежит влассу . Решить проблему делимости - ето значит выяснить, разрешимы ли уравнения о ViJ — \Л / X и V = \Л / в П , где V и W произвольные слова П из К . В настоящей земстве довазываетоя следующая '. <• т е о р е м а . Существует алгоритм, позволяющий узнать для любых слон V й V / в полугруппе П , принадлежащей влассу ^ , раэреш да уравнение (/, = в П илы нет. В |» ;пте [ 4 ] . повезено, что произвольное слово дерева злемен- тарннт врэобрнзоьаняй определяющего слова С- полугруппы Г16 К twe#* вид! '4 1 • • • Х к Q к , (3) - I ОБ -