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

где л - число определяющих слов группы и w = A-lt/r ) , Л = 4 ( У г ) , Ц , \х/г е Q R-t - определяющее слово группы G . ДОКАЗАТЕЛЬСТВО. Пусть г = т а .х / ( RA " 1 £ L £ K ‘ д ; и с и п ^ ’ \х/ = а 7 * а Г г. . г 1 h \ < f r ± 1 > ■ ■>m ; Г ' ; 1 П / 1 1 произвольные слова 4 группы Сг . Для реализации алгоритма решения проблемы сопря­ женности кодирование элементов группы G и МТ определим,как в § 2 ДДя алгоритма решешш проблемы тождества слов. Длина записи слова Т ' У ^ Т W ~1 во внешнем алфавите МТ имеет оценку 1 ( 1 Щ I 1 &г ) 6 (ПЫ-А. ^Ъв к )4o(jzn <-3(п: t h + r 0 K )+ i. ( 22 ) На ленту Ш’ записываем слова tis , Wz ’ и множество опреде­ ляющих слов группы & . Отметим в каждом определяющем слове R- l часть £= jr l( R - ) Далее формируем на втором этаже ленты слово Т и находим ему обратное. В { 7]построены программы для выполнения этих операций. Пусть Л ^ ) = г 4- , i - 1 , г , . , - к . Тогда число тактов на выполнение этих операций потребуется не более, чем icm .t hy4: &on+/i+K'z0 ) -£о£/ъ + (12( f r i t h *к гоУ~< 6 ( m t h t fx7 c ) в n .tl8 (m tk tx z g)+2i(m+htKzob ,кгд< f, SK?t5r. 113. (23) На первом этаже ленты строим слово Т ~ 1 и,\ ~Г . Для это­ го сдвигаем слово к£"' вправо на число ячеек ленты, равное длине кода слова Т , и записываем слово Т . Слева от получаь ной записи запишем слово Т , Число тактов потребуется не более, чем - t u n ^ h ) ^ z h (m t A / K7e){oa*n i-( 6 k ( m + /ii* z o )+ /n i- 2 h t t « г У % П -> 9 h (m t h tx z a ) 1 3 h 1 3 (m t h t Л7д) + 1 (24' К полученному слову T 1 U/ Т it/ 1 применяем алгоритм Лин- 15 -