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

или в и>г на слово 7 ) . Переходам к шагу I в против ;ом случае к следующему шагу. 3. Составляем слова вида т где т=/ Ы , ; к; ( 2 ) -подслово одределя- ■ 2 **' ^ 1 ющего слова R ■ группы; 2 =m.a.oc ; К -число определя- J- ° 1 X j £К / ющих слов группы. 4 4 . Применяем алгоритм Линдона к слову вида ( 2 ) . § 3. Степень сложности алгоритма решения проблемы; тождества слов в классе групп Верхняя сценка сигнализирующей функции времени получена путем построения конкретной МТ для алгоритма решения проблемы тождества слов в классе групп AV£) . Нижняя оценка получена диагональным методом, примененным к рекурсивной последователь- сти групп (G fJ из м а с с а К ( $ ). ТЕОРЕМА I . Сигнализирующая функция времени для решения проблемы тождества слов в классе К ( ^ ) имеет верхнюю оценку не больше, чем t ( m ) ^ К ( 5 # 3 Z m !S+1?4$6'z г п ^ + Ш Э б г я Р ■+ (S 2 3 Z 2 3 -*- О О О +2916^ + 19М г ^ п ъ * -+ (19 f t г* +372 7* +6 3 9 - - 1g. о ) п г°+ (9S6 г* +1236 Za )rri t (162 7*+332 +£ <6г0 w + + (1 }г1+ 2 16г * )т е + (3 3 г * +( З З г 3 +19 z / W +(9 г 3 ~ 3 г, + + 2 ) « t m . 3 + <37*~Пт . )? о £ г г + O ' ( / n f& £ n . ) . < - число определяющих слов конкретной группы Сг е К ( s ) ; п г - длина испытуемого слова в образующих символах группы Q ~ определяющее слово группы (х ; G димаАТМьехни. пусть Or = < а , , • • • > ; * , , • - -, f*K > ; ■■■Q-j.™ && ? ~ t 1 » 1 * h 6 ’г > i * 1 i - i rn а группа принадлежит м а с с у .<(%) . Конструкцию МТ возьмем тац,ю - 7 -