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

0 ± j * k - 1 ) L t J , ro At * A j В G* Слейда работе [5 ], последовательность положительных слов А о . Н , , А,, Нл, А3 > 1 Ak4t Hhj Ак) (3) где к > 0 , назовем базисной последовательностью с^ова Аа , если: 1) каждое Н, является непустым словом, свободным от квадратов; 2 ) Ан Нс*НсАс 3) если 4) существует такое число v из чисел 1 , 2 , . . . к , что Ак ^Ау- (. Две базисные последовательности (3) и В0 . , В,,G-2,..., &т (4) будем считать совпадающими, если I) т = к f =?&L) i k, 3) CrL= HL V i =l,2 ,. .. ,k . в противном случае две базисные последовательности считаются разними. ЛЕША 9 [51. Если в базисной последовательности (3) L(Aa) — р , ТО к * ПР . Действительно, так как & - однородная полугруппа, a L ( A i ) = p Vi =1 , 2 , . . . , k , то существует п р различных слов длины р в алфавите a f , . . . , a a . Значит к < п р . ЛЕША. 10 [5 ]. Для слова А0 длины р существует конечное число различных базисных последовательностей. ДОКАЗАТЕЛЬСТВО, Докажем, что для слова А а длины р ' число различных базисных последовательностей не более, чем ( п + 2 ) 01 , где сх= npL(&)+(nf>+0pt2nf‘+/. ^ Если д базисной последовательности (3) L ( A 0)=p , то длина всей последовательности не превышает числа kL(d)+(k+0 p + 2 k t l f где к к ( л ) - максимально возможная длина олова Н(Н2 .. Нц » ( к + / ) р - длина слова А а, И ,,...,/!* . » 2 k +f - числи за­ пятых. Так как к ± п р , то длина базисн й последователь­ ности для слова А0 не превосходит d . Так как различные базисные последовательности,записываемые как слова,не могут быть графически равными, то для слова А 0 существует не более (п + 2 ) “ различных бази них последовательностей. ЛЕША I I [ 5 ] . Существует алгоритм, который для любого