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

а л л cc П -+1 1 П.+ 1 •) а . а „ а . л а . л. . .. .а . а. л а а. а а ° «с /г-н £ /t+/ с- rv+ 1 1 У п- гъ +1 *- л у у Л - л. + у 7 > С») для л = 0 , 1 , 2 , • •• • Легко проверить, что построенные группы принадлежат опи­ санному классу групп. Заметим, что число определяющих слов в группе G 1 равно 8 , в группе бг, равно 18, в группе равно 2 п? + Ап + 2 и m a xi(R -) = 6 , где £• - определяющее слово любой группы из последовательности ( х ) . Рассмотрим группу Сг и слово 1>УеGi . Пусть £(1&)=пъ Применяем алгоритм Дэна к слову k■/ . Число операций алгорит­ ма Дэна, примененные к слову \х / равно [ * £ ] + * [ f J L f ] < | f / n +9 Строим всевозможные слова вида удовлетворяющие условию 1 ( Т ^ ^ г г ь ( 6 *т .) • / = / , г , „ . А ; £ = 3 . Длина слова ( 8 ) в образующих символах группы G не больше, чем 6 пь + W 8 пъ + 1 8 п ь ( 8 ' ) Применяем алгоритм Дэна к слову ( 8 ) . Число операций, содержа­ щихся в алгоритме Дэна для этого слова, равно 3 m f i -5 tn -L t - 9 п ъ + 8 (3 * 1 * + S t п - l * + 9m xm . 18m . = - 2 9 m -\-869m. +7-97-6гъ t- 199m. tzsszrri t-ini-t-Hi-oni i&nz'. ( 9 ) Согласно (7) и (9) алгоритм Линдона для решения проблемы тож­ дества слов в группе G 1 содержит число операций равное 29rrl,+S69/rf+n$6rriHHm+ZSXn£+3ms+2Wri'-9j-m +*fm. +9 (Ю) Любая МТ, реализующая алгоритм Линдона, для решения проблемы- тождеств слов в группе G :г,:оет сигнализирующую функцию - 9 -