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

Д о к а з а т е л ь с т в о . Запишем Ra в виде A z t R. $ - слово, не содержащее А л . Если R неприводимо, лем­ ма доказана. Пусть R приводимо. Н ^ , .. и , -п р ед ставл е­ ние R у со обязательно ^ 3. /?в - решение ( I ) , то %сть ( A * R ) ^ - A 3s‘4 t ( i= /jY ) , по лемме I стаествгот слова А ? . такие, что и ( Ю Рй= А ^ * ' 4 * ( l - Ш Таким образом, А к является решением системы а , 1 х ^ = л 2 ^ А * .где Н х Н г А< ч А*Н л Н ,К ' Следовательно, по определению система(2,) принадлежит И по определению сдвига . Если W не содержит А ^ , то снова рассматриваем его сдвиг. Так как R предполагалось приводимым; на некотором шаге получим косул«*л^г и 2=-Ал”7F - . Если Р неприводиш, то - искомая коса. Если же F . приводимо, то . снова применяем описанную процедуру. Так как длина час& , не содержащей А3- , все время уменьшается, то на каком .то (bare получим искомую косу. (Если U - слово и &( O ') -<■ д ( А х) , то U -неприводимо). Следующая лемма необходима для получения результата в случае, когда / г , . , / 2^ -переменные. Л е м м а 4. Существует алгоритм, который по двум дапным косам А г В дает решение уравнения л ы = в или выясняет, что решения нет. - . - V Д о к а з а т е л ь с т в о . Очевидно, достаточно доказать существование алгоритма для нахождения натурального решения уравнения А Ы—в . Запишем косу А в виде А~**У . Рассмотрим степени слова Y : У t V * Y 3 , . . Возможны два случая. A. Дня некоторой степени У т найдется слово d ■, такое, что (1Ут = a z 9SC , 3> (S) > £>( 4 *) и S - неприводимое слово. B. Пи для какого У т такого слова С не найдется. I . Допустим,верен случай В. Тогда для каждого У т сущест­ вует слово Ст такое, что &т Y m = ( з ) , где $ т ~ слово, либо приводт,;ое , либо b (s m ) а Э(2А). Всегда можно считать, что верен второй случай. Действительно, если Srn приводимо, то существует слово V n • что TmS^ и д ( 5 т ) < * ( $ т ) , Тогда, беря С,п Ч п . вместо (Am j получим равенство ( 3 ) о меньшим по длине - 120 -