АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

Л е м м а I I . Если при любом п слово В п - неприво­ димо и А - слово фиксированной дайны, то существует сло­ во С , целые q, и р такие, что АЪ* = СВ* р для i. и слово СВ* Р - R -приведено. Д о к а з а т е л ь с т в о . А можно считать неприво­ димым, так как в противном случае, заменяя А на равное ■> ему сл ов о, которое неприводимо, ш лишь у^ныпим длину ело ва А . По лемме 10 АЪ* = A k S Bm , где Ак - начало А , В т - конец В * ’ , | S | < r2 ч V - максимальная длина слов на R , участвующих в преобразовании слова АВ* . Опреде­ ляющие слова, участвующие в преобразовании А В* при силь­ ных R -приведениях и при одностороннем затрагивании А или В * , сами определяются частями А и В * , которые заключены между 1 / 4 R. и 1 / 2 R . Если это часть А, то опре­ деляющее слово иьвет длину, по крайней мэре, мзныцую, чем 4 • |А1 . Если это часть 3 * , то она не может содержать циклической перестановки В 2 , так как в противном случае В и рассматриваемое определяющее слово были бы степенями одного и т о го же слова, что влечет противоречие о неприво дикостью Ъ° для любого целого л , Поэтоцу дайна рассмат­ риваемого определяющего слова, по крайней мере, М экъпе 8-|В|. Если же £ преобразовании АЬ* применяется R -при­ ведение, заьвняемая часть которого захватывает части А и В * , которые меньше 1 /4 R., то оно единственно и приюИяет- ся сразу после сильного ft. -приведения. Поэтоцу определяю­ щее слово либо меньше 8-\А|, либо меньше 1б|В|,так как за­ хваченная часть В* в этом случае не может, в силу условия Т, содержать циклическую перестановку В>е . Если же в последовательном преобразовании АВ+ приме­ няются ft -приведения,Не затрагивающие ни начала А , ни конца В * , т о , как это следует из рассмотрения переходов от слова ( I ) к словам (2)~ ( 4 ), в таких f t -приведениях ис­ пользуются только слова, которые использовались ранее при f t -приведениях, затрагивающих начало А или конец В*\ i аким об р 'зом , г в ферцулировяе лемш 10 ограничено и - 28 -