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

- « « у [ '* 4 ойладает по меньшей мере одним ¿ г _ слово,, относительно полного сп особа сокращения [ У, £ 7 , причем если только одним, то <*' _ словом 1 -г о рода. Алгоритм Дэна состоит в следующем. К данному слову МЛ прИме. няем до тех пор пока это возможно операции^ °У сокращение^ Р / замену X на У , если Л л Х У и 1 ( Х ) > С ( У ) Ввиду теорецы I \У=-/ в С тогда и только тогда, когда этот процесс закончится пустым словом. § 3. Доказательство теоремы I " Доказательство теоремы проводится индукцией по числу сомножи­ телей 7 ] / ? ; Т , в £ /, ¿ 7 » основывается на доказательстве в леммах П-Х: ряда утверждений. Ради удобства в формулировке лемм для этих утверждений введем следующие обозначения. А и . . Пусть и , 1 $ ! < к $ £ , Тогда при любом способе сокращения слова £ / , к ] оно обладает по меньшей мере одним /г - словом, причем если только одним, то это 1 & - слов*о 1 -г о рода, взаимодействующее в [ ¡ , к ] не более чем с одним /? слев* и не более чем с одним /? . оправа. Вц. Пусть ¿ - / и , , Л £ £ , Тогда при любом способе сокращения слова 7^ И Тк не участвует в его сокраще­ нии. ; • >■ В и. . Пусть Ь ¿ и . , i $ J < к $ ь и пусть при А с с [ 4 , * ] слово +/ , К - 1 ] полностью поглощается, взаимодействуя хотя бы с одним из слов Я ; , Д* . Тогда либо И ни с чем более в [ ] 1 к ч ] , либо г"* 1 Я к -1 и ни с чем более в [ ( к ] V