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

Содержание этих лемм дает оценку сигнализирующей функции вре­ мени алгоритма Дэна для решения проблемы тождества слов для класса групп G < ' £ ) . Группа принадлежит , если она конечно определена и множество определяющих слов симметрийо- вано и имеют меру налегания ^ $ . Решение проблемы тождест­ ва слов для этого класса принадлежит Гриядлингеру L 8 J. Мы сформулируем результат объединяющий содержание л .1 и л . 2 . Сигнализирующая функция времени для решения проблемы тож­ дества слов в классе G ( £ ) имеет оценку. +S u n +3%*-1)&ц:1/г-+т /< (625т '+ 2/пг + 1 ?,ZSrru + ° ил. ' о ■> +18г ^ + н г - У)£оя п + п ъ к а о 8 ? 5 т \ б г т + г .9 ,^ S z z+ 3 S , 3 ?S/m о о ^2, > V 7 О 7 +гЪХ,57.0 + О, 75 "), К - число определяющих слов группы G £ G С$ ) , гь -число образующих символс j группы G , Za =r r u ^ .x ^ ( ^ п г ~ ДО™3- испытуемого слова в образующих символах группы. § 2 . Алгоритм решения проблемы тождества слов и сопряженности в классе групп Линдону принадлежит следующий результат. Пусть F - конечно порожденная свободная группа, R - конечное симметризованное множество элементов ( , /V -н о р ­ мальное замыкание R в F . Бели R удовлетворяет условиям С ( 6 ) шш С [А) и Т ( 4 ) , или С (3) и Т ( 6 ) , тогда пробле­ ма слов для G ~ F / M разрешима. — M l рассмотрим группы, удовлетворяющие условию С ( 6 ) . Уело- 4 вие С ( 6 ) для таких групп о н а ч а е т , что множество определяющих соотношений каждой группы имеет меру налегания £ , Ранее нами был рассмотрен класс групп, множество определяющих соот­ ношений которых симметри 8 оьсшно и имеет меру налегания ■< | - Для этого класса групп найдена верхняя оценка степени сложности алгоритма решения проблемы тождества слов и сопряженности слов [ ? ] . Алгоритм решения проблемы ■ ждества слов для групп, удов­ летворяющих условию С ( б ) в соответствии с результатом Линдона - 5 -