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

что существуют такие отрезки J o и , что Pq 30 для некотороых и У= .Так как олово и зъ я в л я е т с я отрезком, то из максимальности 5^ в слове У следует, что i , откуда ij? ? и 3 ^3 j =Л , а , следовательно, и 3 j = ?q .Таким образом, в (г* имеются следующие равенства 3 q A p j= * p j5 q , X -?T t y ; J , и , наконец, ^ 5 £ =. б(А^^Ар}.Поскольку "ЬСЧ)^ т - , то к последнему равенству можно применить индуктивное предполо - жэние, из которого получаем, что Ь= н2 к4 . . . Н* • где для любо­ го т- H i, - отрезок и существуют слова /4< \ - ■■ Рчб такие, что Арз —Арз » ~ An , a pi И г ' НгАп С л = а ^)- Для доказательства леммы осталось обозначить ? е через Hi , д ^ через ftfjj . Лемма доказана. ОПРЕДЕЛЕНИЕ 3. Последовательность вида Л -<в\ ' Н 4 , * < * » , . . . н * , ' < б) йудем называть базисной последовательностью, соответствующей кор­ тежу А**'* . если: 1 . V \ (Ч=\Г*) - непустой отрезок 2 . * т (а= М=3 A ^ V ^ i f t ' в G-* 3. Для любых фиксированных t i , г г 1 Ч 4 г и к - ь 4. 3 v e ^ i , J L . . . vt^ f ct *' ЛВММА 9 .Для базисной последовательности (6) выполнено соотношение 4 ^ Г*Л ДОКАЗАТЕЛЬСТВО. Действительно, так как 6 + - однородная полугруппа, а суммарная длина всех слов кортежа ~к ) равна 3. , то существует не более к* кортежей оуммарной длины! в алфавите с ц ,. . . а*, различных, удовлетворяющих определению базисной последовательности. Значит , к ь к * . ОПРВДЗШИЕ 4. Базионым оловом будем называть ОЛОВО Н 1 . ■. И * НтгД, ----- Н J 1 Легко видеть, что число всех базисных последовательностей вида (б) ограничено .Поэтому, используя алгоритм, решающий пробле­ му равенства слов в 6 , мы получим алгоритм, который для всякого кортежа выписывает вое различные базисные последовательности и , следовательно, все базисные олова, соответствующие этому кортежу. 161