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

2 ) s ( p ) - слоговая длина слова Р , то есть если Р в а-; . . . а% , V,- > о , £ * Vw,T0 S ( Р ) = к - При этом должно выполняться условие: для ^любого L Ai =^дг£А Л/>( <^> Bi = a.<i Bi <Хр; • з ; S ( p ) - число вхождений какой-либо фиксированной буквы в Р . Эта функция была использована в [ i j . а ) Пусть Р 3 р< a li Pt a l t . .. Рл а е' РЛч , не содер­ жат Л , i j > О . Тогда S ( Р ) - п . Условие: для любого С _ А{ « a At <^> a Bi Ai а А; а <г*> B-L - B-L Л . 5^ Обозначим через Л* (соответственно RK) некоторое не­ пустое собственное начало вконец/ слова R . SCP) - число вхождений некоторого фиксированного слова R в слово Р . Если R - яе гиперпростое (гиперпростым назы­ вается слово, у которого никакой собственный конец не совпадает с началом [ 2 ] ) и его вхождения в Р пересекаются, то считаем каждое вхождение отдельно. Условие: для любого i и любых R , R А[ - R KA * & B i ~ R Kb ? * А - м Г л " А Т : б) - фиксированное непустое слово. Определим квазисте­ пень слова R (обозначается [ В ] ) индукцией по длине I R ] . Всегда В ( [ Rl) >, д ( R ) \ д ( [ R] ) = д (R ) [ R] = R .. Пусть теперь Т - квазистепень R ■ , 1 4 д (Q) £, д ( R ) . ^ Тогда Т Q - кваэистепень R , если и только если сущест­ вует слово X (возможно, пустое) такое, что Т = , R . s X Q . Для гиперпросторо Л понятие квазистепени сов­ падает с понятием степени Я . Пусть Р = Pf L Я ] Pj [ Я 1 ■■■ Рл [ Я] В,., (здесь в Р выде­ лены кваэистепени слова R максимальной длины), Ру не содержат [Я] ; тогда S ( Р ) - П . Условие, как в примере 5 (но тут R и R могут совпадать с Л ) . 7 ) Пусть /V * { Сг , 5 - некоторое множество различных слов в алфавите U. . Допустим, что Л/ удовлетворяет условиям: а) К с /V ; ГГ