Ученые записки математических кафедр вып. 1970 г.

Пусть даны элементы V, V , , ■■■ I£ . На основании леммы 2, можно эффективно найти конечные мн*Е жества Лю.» и \ /-П ~П ,и П £ причем если и / е Ц , те Ш У 1 ■ если 1Ы Л\ * . . . Пусть «V•- сх'^ ~ТеVи Ц.еЛ. ( Спомощьюалгоритмов для решения проблем тождества слов и обобщенной делимости для полугрупп можно выяснить? содер* лит ли Т элементы Ы£ без пересечения так? чтобы Т равнялось в А произведению 11^ и элементов длиныI.’ Если потребовать? чтобы соседние элементыдлины I принадлежа*! различным то из условия в) следует; что существует конечное число таких разложений элемента ”Г и их можно эффективно найти. Теперь остается применить алгоритмы для ремения проблемывхокде& имя для полугрупп СЛг\ чтобы узнать? равняются ли полученные элементыдлины I произведениям элементов иэ /Ч . Лемма 3 доказана. Лемма А.' Полугруппа СУ удовлетворяет условию в). Доказательство." Сначала покажем,1как решить проблему левой делимости для СУ ? идокажем“; что в СУ чвсло правых обратных для делителя относительно делимого является конечным м вх можно эффективно найти. .ч Пусть даны элементы В ■ О . Для того? чтобы выяснить? существует ли элемент У _ такой'; что 0 = Б У , найдём по лемме 2 конечные множества О И В Если Ц 6 0 я 1/б 'В ? то с помощьюалгоритмов для реиенмя проблем тождества слов и левой делимости для полугрупп С£г ( -/<•"£.< ПУ, легко уэнать?< ямяетоя ли V левым делителем и в а .* Если дат, то конечность числа правых обратных для делителя относительно