Алгоритмические проблемы теории групп и полугрупп. 1994 г.

которое назовем специальным. Для краткости будем называть специальным и сам моноид М , имея в виду его фиксированное копредставлегше ( 1 ) . Предположим, что для (1 ) выполняется свойство Черча—Россера: произвольные слова X ) У равны в М тогда и только то гд а, когда существует слово 2 , полу­ ченное из X и из У одними сокращениями ("под сокращениями понимаются преобразования вида Рк^О.'^’ Р<Р ) . Тогда будем называть М моноидом Черча-Россера. Назовем слова Р< , к г .......... Рс . . . . определяющими слова­ ми. Будем говорить, что слово X неприводимо, если оно не со­ держит -в качестве подслова никакого определяющего слова. Из определения непосредственно следует, что каждый класс равных слов в специальном моноиде Черча-Россера содержит ровно о,дно неприводимое слово. Поэтому результат полного сокращения лю­ бого слова не зависит от порядка сокращений. Мы будем использовать следующие обозначения: 1X1 - длина слова X ; = - равенство в моноиде М ; э - графическое равен ство; 1 - пустое слово; < X, У, > - подмоноид, порож­ денный -элементами Х,У} . ■• в М . Под собственным началом (концом) слова будем понимать начало (кон ец ), не совпадающее со всем словом. Слово X назовем простым, если его' нельзя представить в виде Х г S ‘l при а > / . ^ Некоторое начало слова А часто будет обозначаться А ; некоторый конец - • Если не оговорено противное, то А я А ^ А * 1. Слово X назовем двусторонним, если в ( 1 ) существуют определяющие слова вида У X и X Т . § 2 . Вспомогательные утверждения Без ограничения общности (см . теоремы 1 .2 и 1 .3 из [2 Р ] ) можно считать, что множество определяющих слов Р, , Р а , » . . , удовлетворяет следующим двум условиям: 1 . Для любого у /Яу/ > / 2 . Если £ ¿ 5 Р к; а , то Р г <2 г / . Тогда нетрудно доказать следующую лемму. ЛЕММА. 1 [ 2 0 ] . Если в копредстатшзшш ( 1 ) спецу ахьчого моноида Черча-Россера имеются определяющие слова А В и 105