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

ясно . ч т о д ( а нУ±1c i t l х ^ ) > 1 <р> д с а * и поэтому •trp По предположению, имеем d ( v ) ^ р ■, С другой стороны, d ( W i ) & L P двух неравенств следует, что -Р е , где О = Э с ^ * ) . И з последних д ( \ / ) / э ( WL ) 2 р + е / С р + е , отсюда Z дС V ) 2 - о> ZJVy ) но < д L и L д ( V ) & т L , следовательно, п г С < L Э ( V ) * л ь L . Получено противоречие. Допущение о том, что V G Q.-, неверно. Множество М * конечно, и мы можем эффективно найти все его элементы. Ясно, что оно содержит лишь конечное число элементов, равных W в OZ и имеющих длину & /7г. , следовательно, меньших и п г С , Лемма 3 доказана. Справедливость теоремы непосредственно следует из леммы 3. ЬАЫъЧАШК . Существенность требования разрешимости проблемы делимооти в свободных сомножителях следует из следующе­ го примера. Пусть полугруппа O t i задана образующими Q., QI , и опре­ деляющими соотношениями А г = в с . С/ 1 г задана образующими € , и определяющими соотношениями С у , причем и в = в , • Легко проверить, что фактор-полугруппа 01 = СЛ,* <Лг / у г - < а , а „ е, вр, Ai - В- , Су = 4 , С1 7 б о ~ - a f 6 7 / l > принадлежит классу / С ' . Пусть X . e O l t . Утверждение а 78 х = Q ? X в O t тогда и только тогда, когда X делится на CL слева. Действительно, пусть л" делится на (2 , т .е . Х ~ О У тогда а , в к = a , S a y = а 7ё 7а у = а , в,х> Пусть теперь С17 в X = Cl, X в 07. , Из этого соотношения видно, что X должно делиться на Q. слева. Утверждение дока­ зано. ЮГ