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

- К ( О) в любом случае; - К ( i ) , если из того, что С - кусок, следует, что С. не имеет внутренних вхождений; - К ( 2 ) , если выполняется следующее: 1. йэ того, что- С - кусок, следует, что С имеет только полные вхождения; 2 . Из того, что С - Q г - плоское произведение двух кусдов, следует, что хотя бы один из кусков Q 1 , Ot имеет только односторонние вхождения; - К ( т ) , т £ Л/ , т > 3 , если выполняется следующее: I • С = Qi ■ .. Q р - произведение кусков при р < т - < влечёт, что это произведение не плоское; 2 . Если С £ Q m-Y ~ плоское произведение кус­ ков, то Q< и Qm .< имеют только односторонние вхождения; 3 . Если С = 0^ . .. Qm - плоское произведение кус­ ков, то хотя бы один из кусков QY , Qm имеет только односторонние вхождения. Пусть теперь полугруппа (1) удовлетворяет следующим усло­ виям: 1) Все определяющие слова непусты. 2) Существуют рациональное число М> О и функция длины S на полугруппе П такие, что для любого определяющего соот­ ношения А; = в ; а) A't. удовлетворяет условию К ( т г) , где т< > -fa i S ( & i ) ~ S ( A i ) ] + 1 ; б) удовлетворяет условию К (т л ) , где > J f L S f c i - U S ; ) ] + 2 . 3) Если хотя бы одно определяющее слово не удовлетворяет условию К ( 2 ) , то система определяющих соотношений полу­ группы не имеет циклов [ 10 ]. Мы хотим доказать, что любая полугруппа, для которой вы­ полнены эти три условия, является F E С -представленной. Нетрудно понять, что произвольная полугруппа принадлежит классу Е.В.Кашинцева тогда и только тогда, когда все её опре­ деляющие соотношения удовлетворяют условию К ( 2 ) к выполня­ ются наши три условия. Чтобы это доказать, надо заметить, что в обоих классах определяющее слово может быть куском только ес­ ли все его вхождения полные и что на любой полугруппе можно з а ­ дать функцию длины, тождественно равную нулю. В6