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

б ) для любых I , у собственное начало Q не совпадает с собственным концом Су , Тогда множество /V назовём словарно-гиперпростым (СГ-мно­ жеством). Пусть Р — А 1 у, ■■■A/ук - представление слова Р в виде произведения слов из некоторого СГ-множества Л/ . На* зовём это представление CP-разбиением Р относительно /V , если не существует представления Р s A/lt . . . А //^ при п к к . СГ-разбиение любого слова относительно фиксирован­ ного СГ-множества существует и единственно. В качестве Р СР) можно взять длину СГ-разбиения слова Р Условие: если слово Cg 4 . .. Cg является собственным кон­ цом /'началом) некоторого Ср £ N , то СГ-разбиение /I, начинается /кончается) с Cgt . .. Q r тогда и только тогда, когда P>i начш ается /кончается) с С/, ■- - Cgr . _ 8 ) Зафиксируем какое-либо разбиение алфавита 14 на не- пересекающиеся подмножества 14 = 14 < U Н г U . . . U 14 т . Алфавитным разбиением длины t слова Р назовём представление Р= R< ... R t , где каждое RL есть слово в алфавите р с й т )\ причём R{ и - слова в разных алфавитах для всех I . Тогда S ( Р) - длина алфавитного разбиения Р . Условие: слова А [ и P>L начинаются /кончаются) бук­ вами из одного алфавита Uр ( 9) Пусть 1lt , Hg - непустые непересекающиеся подмно­ жества алфавита 14 . Обозначим через t u у ( Р.) число вхождений букв из 14у в Р , Правый /левый ) индекс слова Р относительно пары / И л ) равен сумме количеств вхождений букв из Й г в Р еправа /сл ева) от букв из /суммирование по всем вхождениям букв из t t f в Р ) . Тогда S ( Р ) равна правому /или левому) индексу Р относительно / 11, f 1lt ) . Частный случай етой функции был использован в [3 , с .. 32J . Условие: для любого L t ( A-i ) * t u . ( В( ) , 10) Пусть Р * aJ . ' a U ' - > V * Ь +i > К > °- Рассмотрим слово p * * a , ,a i t . .. аи , полученное из Р при­ равниванием всех ty к единице. Пусть R — Ру, йуг . . . Qук , К > 4 , J P * Р р к ■ # Тогда S (f>) равна числу вхождений слова R в Р . Условие: • А : н R k ( A * ) k <*> А ? » Я * ( ф * 78