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

положительного слова Д0 выписывает все различные базисные последовательности этого слова. Следуя [5 ], будем говорить, что базисная последователь­ ность (3) порождает базисное слово w (6) Это определение вместе с определением базисной последо­ вательности указывает, как по базисной последовательности строится вполне определенное базисное слово. Говорят, что И/ есть базисное слово, относящееся к слову А , если существует базисная последовательность сло­ ва А , которая порождает базисное слово W . Базисные слова, относящиеся к одному и тому же слову А , называют совпадающими, если они равны в группе G , и различ­ ными, если они не равны в С . ЛЕММА 12 [ 5 ]. Если L ( A . ) ~ p , то существует конечное число базисных слов, относящихся к слову А о . ДОКАЗАТЕЛЬСТВО. Докажем, что существует не более чем (n+f)i? , где $= 2 .п р L (A ), различных базисных слов, относящих­ ся к А0 . Действительно, если в базисной последовательности (3) дСА0)~Р , то длина порождаемого ею базисного слова не превышает числа 2 k L ( A ) , так как L (H j) ^ L ( A ) V j , причем по лемме 9 к ^ . Следовательно, длина базисного слова не превышает числа 0 - 2 п . р L {& ) , и существует не более чем (П+01* различных базисных слов, относящихся к сло­ ву До . Из леммы I I и теоремы Артина сразу следует ЛЕММА 13 [5 ], Существует алгоритм, который для любого положительного слова А 0 выписывает различные базисные сло­ в а , относящиеся к слону Аа . ЛЕША 14 [ 5 ] . Пусть А - любое положительное слово, и пусть W(l Wj Wj _ список всех различных базисных слов, относящихся к слову А . Тогда среди слов VV,, W Щ либо найдется слово, равное слону А2 в G-* , либо найдется олово, равное А в G Следующие две леммы являются аналогами лемм работы [ 5 ? . ЛЕША 15. Если W - базисное слово, относящееся к А0 , то 4„W=1V40 в группе & . - 88 -