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

а) <? В ,, - K j n ^ - определяющее соотношение; б) ^ & yy = Y‘/ t t " 4 , ■ Рассмотрим случай а ) . Можно применить условие Т ( «'У,^пола­ га я {'см. определение 3 ) ; Н, - К /+ / Z-t * £ f y t f } E t - Yi/+t J t = 4 , Получаем X г С, Ч +Y > в в Y * Л У ,/ ^ LJ +Y ^ i/ YY ^CjYY , *^CJYY F^ ii+ J — K'S+l Рассмотрим случай б ) . Если А -®v+/ & К у ,, » то либо *>Ц и явл яется собственным началом Куч* * либо наоборот. Но тогда одно из определяющих слов - £<уч* Ку>, -Ay*-/ и л и Y ij Y i j + y Y / t i - явл яется произведением .tjpyx ку сков. Следовательно, в любом случае 2 * 1 /+ y s К уч , . Кроме того, А/+, - ^ , иначе опять получаем противоречие с определением полугруппы рассматриваемого к л а сса . Таким образом, в. любом случае £ = Е*уч> ^ и из индуктивного предположения и симметризованности Мп опять получаем, что A y 'A v А у ~ В - определяющее соотношение ч / y - i Q 'S + f или A y Xty Ay = F •L Слово F становится новым Ку>/ Y rv - НОВЫМ ' t j , K / t t - НОВЫМ Yc/+1 И Т.Д. 3 . £ п ер есекается c P c-t и 77 (симметричный случай р а с­ сматривается так же). Слово P c - y непусто, иначе получаем случай 2 . Так как Сс, = Л , то £ не может захватывать все слово К, Тогда £ — Р"-, К / , Pc * - P c - y P-i'-r > К / - К / Ycn, , Yc* - к у со к , У," * Л . В этом случае Е й F играют роль новых определяющих слов А ч У ч в / , и A y У с, (£>с, , причем А /, - С-с, - ®<ч - А , A y s А-/ > A , s К , • Слово будет новым Л ,-, Свозможно, пустым). Все утверж­ дения леммн, очевидно, выполнены. . . 4 . £ пересекается с Я(-< , А , Рс . Тогда К у - кусок и определяющее слово K'f - произведение двух ку сков, т . е . этот случай невозможен. . 5 . В пересекается с 7 j , P i , . £ не может захватить V7 * t и Км/, г целиком, поэтому 1 £ * л,- У,и,< , Yiic * л > Ус"<, > * л > Y,Ki и У, , - куски. Тогда £ и F становятся новыми А ,/ У с/ А у и Сс / Y ,/ £> ,/ , где А / - К , А , = А , б (> - Y in ,i ) £с/ ~ Л 72