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

В классе К ( 5 ) существуют группы, например, G 1 , Qz , для которых оценка степени сложности алгоритма решения проблемы тождества слов является оптимальной. Действительно, можно построить ГЛТ, реализующую алгоритм решения проблемы тож­ дества для этих групп и , сигнализирующая функция времени для которой тлеет равные верхнюю и нижнюю оценки с точностью до постоянной. Внешний алфавит МТ зададим так: 6 , л , ® } Определяем кодирование элементов группы Gf^ , используя соот­ ветствия: а , - л , ; а / - * а * ; сС’ - 'а г * ; Качало и конец слова W ccl ^ cl ^ ) е G 1 отметим на ленте символом ® . Предположи!.!, что слово ^ г а . „ а г ) циклически не­ сократимо и длина слова t^- ча в образующих символах груп­ пы (rj равна т , . Получаем оценки длины слова № ( а .^, а £ ) во внешнем алфавите МТ L ( ^ ( a i y a.t )) ^ Z m . Проверяем содержание части определяющего слова R. •в слове №( а „ й , ) . Сдвигаем определяющее слово R- группы G вдоль слова Iv c a ^ a ,) и посимвольно сравниваем записи слова и R. . Учитывая число определяющих слов группы йг и получаем число тактов не больше, чем ^ 2 - г т .- 2 . г - 8 = 2 . 88 пх. ( 18) После каждой замены части > ) определяющего слова Я£ производим свободное сокращение полученного слова. Для этого сравниваем считываемый символ со следующим символом, если они совпадают, то проверяем,является ли следующий символ символом х . Если следующий символ является х , то стираем символ х и два предыдущих символа. В противном случае считывается следующий символ и сравнивается с последующим символом. Символ конца за­ писи слова к /( 0 -^а.£ ) делает останов МТ. Число тактов на сво­ бодное сокращение, т. е . удаление подслов видя cl . cl . ,сС 1 а-. f потребуется не болео, чем t ivn) ±; 2 rn. +Чгп Число тактов 1 ш виполнише алгоритма Дэна, примонешюго к слову W , потребуется, согласно ( l b ) , ( I S ) , не больше,чем (19) - 12 -