Тема: Некоторые гипотезы о морфических словах

Данная работа посвящена некоторым гипотезам из такого раздела математики как комбинатора слов. Основными объектами изучения будут слова (конечные или бесконечные) над конечным алфавитом, а также морфизмы, то есть гомоморфизмы моноида слов. Любой морфизм естественным образом продлевается до определённого на множестве бесконечных слов. В работе изучаются так называемые морфические слова, то есть бесконечные слова, полученные как предел последовательности конечных слов а, f (а), f2 (а), • • •, где a- буква рассматриваемого алфавита, а f - морфизм, такой, что f (а) = аи, где и - непустое слово. Тогда в последовательности a, f(а), f2(а),... каждое предыдущее слово является собственным префиксом следующего, и, таким образом, эта последовательность определяет некоторое бесконечное слово, которое притом будет являться неподвижной точкой морфизма f.
Построение бесконечных слов в виде неподвижных точек морфизмов является одним из основных способов в комбинаторике слов. Одним из его преимуществ является возможность порождать слова быстро. Несмотря на то, что не каждое бесконечное слово является морфическим, очень часто свойства бесконечных слов, например, свойства периодичности (обыкновенной [3], [4], абелевой, слабой абелевой [2]), свойства избегаемости (см., например, [15], [16]) изучаются именно на морфических словах.
Активно изучается вопрос комбинаторной сложности (или просто сложности) морфических слов. Сложность бесконечного слова и - это функция, сопоставляющая каждому натуральному числу n число различных подслов длины n в слове и. Абелева сложность - то же, но подсчёт ведется с точностью до абелевой эквивалентности подслов (два конечных слова называются абелево эквивалентными, если одно можно получить из другого перестановкой букв, иначе говоря, если для каждой буквы алфавита верно, что число её вхождений в одно и в другое слово совпадают). Оказывается, что задача об абелевой сложности морфических слов трудная, она активно изучалась и есть много частичных результатов (к примеру, [6]), однако об абелевой сложности морфических слов всё ещё известно мало. В настоящей работе, в разделе 3, мы будем говорить о таком связанном с абелевой сложностью свойстве морфических слов как абелева периодичность.
В настоящей работе изучаются два вопроса: когда морфическое слово является словом Линдона, и когда морфическое слово является абелево периодическим.
Ответ на первый вопрос в случае, когда алфавит состоит из двух букв, был дан в [1]. Однако характеризация, полученная там для бинарного алфавита, не может быть сразу обобщена для случая алфавитов больших размеров. В разделе 2 настоящей работы показано, что условия критерия линдоновости неподвижной точки бинарного морфизма, полученные в [1], образуют избыточную систему. При этом при избавлении от одного из избыточных условий получается сформулировать уже жизнеспособную гипотезу о критерии линдоновости неподвижной точки морфизма над алфавитами размера 3 и более. Слова Линдона, конечные и бесконечные, оказываются важными даже в на первый взгляд не связанных с ними задачах. Так, свойство линдоновости сыграло важную роль в доказательстве «runs conjecture» [11], которую до этого не удавалось доказать на протяжении 15 лет. В свою очередь свойство линдоновости для бесконечных слов связано с некоторыми другими изучаемыми свойствами бесконечных слов. Например, линдо- новость для бесконечного слова является достаточным условием отсутствия самошаффлуемости [12].
В разделе 3 настоящей работы мы говорим об абелевой периодичности морфических слов. Об этом свойстве известно мало, в то время как известна разрешимость, в случае бинарного алфавита, задачи о более слабом свойстве морфических слов, а именно: о слабой абелевой периодичности [2]. Кроме того, разрешима задача о периодичности в обычном смысле для морфических слов [3], [4].
Со свойством абелевой периодичности так или иначе связано много других свойств морфических слов. Морфизму f на словах над алфавитом Е = {ai, a2,... an} можно сопоставить матрицу M размера п х п, где коэффициенты этой матрицы mij = |f(aj)|ai, то есть количество вхождений i-ой буквы алфавита в образ j-ой буквы под действием морфизма f. Например, f (а) = амЬ пусть Е = {a, b}, тогда морфизму
f (a) = aab
f (b) = bbaab
будет сопоставлена матрица
2 2
1 3
В терминах собственных векторов этой матрицы можно найти плотности каждой из букв в слове, порождённом данным морфизмом [5]. Заметим, что у бесконечного абелево периодического слова плотности каждой из букв рациональны. Поэтому иррациональность плотности какой-нибудь из букв морфического слова даёт достаточное условие отсутствия абелевой периодичности.
Кроме того, в терминах собственных чисел описанной матрицы можно частично отвестить на вопрос о с-сбалансированности соответствующего морфичного слова. В сложном случае одной информации о собственных числах матрицы может быть недостаточно, тем не менее, известна характеризация морфизмов, порождающих с-сбалансированные слова [7]. Свойство с-сбалансированности также является необходимым условием абелевой периодичности.
Структура дипломной работы организована следующим образом. Секция 2 посвящена вопросу о линдоновости морфических слов. В разделе 2.2 доказывается избыточность системы условий в критерии линдоновости для бинарных морфизмов из работы [1]. В разделе 2.3 сформулирована гипотеза о критерии линдоновости морфизмов над алфавитами размера 3 и больше, а также получена простая оценка на константу, возникающую в этой гипотезе.
В секции 3 рассматривается вопрос об абелевой периодичности морфи- ческих слов. В разделе 3.1 приводится классификация морфизмов длины не более 6 по свойству абелевой периодичности их неподвижной точки. В разделе 3.2 обсуждаются необходимые условия абелевой периодичности и от- {f (a) = ab, доказывается отсутствие f (b) = bbaa абелевой периодичности у порожденного им слова, притом что известные необходимые свойства абелевой периодичности для этого слова выполнены. В разделе 3.3 найдено достаточное условие абелевой периодичности морфи- ческого слова и сформулирована гипотеза о его необходимости.
Купить

В настоящей работе были рассмотрены две задачи о морфических словах: об их линдоновости и абелевой периодичности. Доказано, что в результате Ришомма и Зеболда [1] система условий, составляющих критерий линдоно- вости морфического слова над бинарным алфавитом, является избыточной. Это дало новую формулировку критерия для бинарных слов, на основе которого сформирована гипотеза о критерии линдоновости морфических слов над алфавитами размера 3 и более. Отметим, что исходная формулировка Ришомма и Зееболда не допускала естественного обобщения на алфавиты больших размерностей, что авторы отмечают в заключении статьи [1]. Кроме того, была предоставлена классификация коротких морфизмов по свойству абелевой периодичности их неподвижной точки. Приведены некоторые необходимые и некоторые достаточные условия абелевой периодичности в общем случае, а также сформулирована гипотеза о необходимом и достаточном условии абелевой периодичности морфических слов. Обе гипотезы были проверены на коротких морфизмах.
Купить