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

веденного слова SQ . Поэтому R -приведение слова ( 4 ) дол­ жно было бы захватить, по крайней мэре, одно из слов В ' и Q1 и затронуть Ео или Из соответственно. Однако это невозможно по леммэ 5. Следовательно, слово (4 ) (^.-приве­ дено. Случай 2 .2 .2 . Слово BQ R -приводимо. Проведем R-привзДения слова A,|&QB.| , затрагиваю­ щие одноврешнно и S , и Q . По лемме 4 захваченный ко­ нец S мзныие 1/4 R . Поэтому заленяемая часть R -привел дения захватит начало Q , которое больше 1 /4 ( I , а , следо­ вательно, захватит все Gj . То есть R -приведение прои­ зойдет при помощи определяющего слова Q B c (Т 2 • Если бу­ д ет затронуто , т о , по условию С /1 /4 /, Ь , и Во име­ ют непустое общее начало, что противоречит свободной при­ веденности слова Во . Таким образом, заменяемая часть рассматриваемого R - приведения состои т из конца 8 и в се­ го Q . Цусть SQ = & 4 . 8 aQ,^ S , T • Тогда ишем три последо­ вательных R -приведения: &СсЪс = AiA^C^ C g B ^ ~ у _ ^ а Х с Л в ^ а ; шэ в , = д а з . откуда q b ; c 2 ~ q t s 2 И AoC,,S~ является определяющими словами. В зависимости от соотношения длин Вс и Т рассмотрим два случая. Случай 2 .2 .2 .1 . Т\ , то е сть В ^ - Р Т , S 2 - РС 2 • Если P-j* I , то R. -приведение слова A cC cE t^ A ^ C g P T B ., при помощи определявшего слова Д 'С ,С аРй^ одноврешнно затрагивает и А,, и Ъ с , что противоречит условию, пололенноцг на ( i ) . Поэтоцу Р - I , то е ст ь К .^ Т , vSg^CTj , (?Et'C2 и A ^ C g ^ e R Иш - ем А оС сВ о = А^Ар ,С 2 Вс,В4 ^ А н А с С ^ В ^ ^ • ♦ А ^ & .В и • Однако слово А ^ В ^ В /® A^S^Bo мо»вт быть получено из АСР 0 ЬС при помощи одного R -приведе­ ния, а именно: A cC cB c^AXC&B c , где S<Bt - R -приведено, так как в противном случае R. -приведение произошло бы при помощи определяющего слова , так как В о > 1 / 4 R , и имели бы свободную приводимость C 4 S 1 , что невозможно в силу существования определяющего скова - 25 -