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

Непустое слово S называется слогом слова AS&, е с ­ ли для любого определяющего слова ST у Б и Т нет непус­ того общего начала, а у А и Т нет непустого общего конца. Слог называется неправильным, если он пересекается с каким- либо другим слогом данного слова. В противном случае - пра­ вильным. Непустое пересечение двух неправильных сл огов на­ зывается границей. Замена в слове W слога S на слово Т называется. d - приведением слова W , если . Слова S в Т назы­ ваются соответственно заменяемой и замещающей частями. R -приведение с лова W называется сильным d -приведе­ нием, если Т L 1 /4 R . В противном случае - слабым R -при- ведением. Из введенных понятий естественным образом следует поня­ тие R -приводимого слова._ Выражение АВС — ""ADC означает, что слово ADC полу­ чено из АЬС при помощи одного R -приведения с заменяе­ мой частью В и замещающей частью I) , Причем о подслове слова Е будем говорить, что его затрагивает данное R - приведение, если Е и Ь имеют непустую общую ча сть, если же Е = В , т о , кроме т о г о , будем говорить, что е г о захва­ тывает данное R -приведение. Слово А называется неприводишм, если не существует рав­ ного слова с меньшй длиной. Очевидно, что если А - не­ приводимо, то А - R-приведено. По левое I имеем, что всякое сл ов о, равное единице в GI, может быть преобразовано к пустоцу при помо!ци свободных при­ ведений и R -приведений. Л е м м а 3 . Пусть W - свободно приведенное сл ов о. Если R -приведен: е с непустой завещающей частью преобразует слово \У в слово U , то U также свободно приведено. Д о к а з а т е л ь с т в о . Пусть W - АВ С— ■"АпС^Ц. Коли U свободно приводимо, т о , в силу свободной приведен­ ности W , свободные приведения слова U возможны только в АН и в НС , где Н^1, что противоречило бы определению сл ога . - чп -