Тема: Об абелевых свойствах морфических слов

Комбинаторика слов — это сравнительно молодая область дискретной математики и теоретической информатики, основным объектом которой являются конечные или бесконечные последовательности символов из конечного алфавита, называемые словами. Комбинаторика слов тесно связана с разными разделами науки как внутри математики и информатики, так и за их пределами. Среди областей применения комбинаторики слов следует особенно отметить теорию автоматов и формальных языков, а также алгоритмы на строках.
Одним из разделов комбинаторики слов является изучение абелевых свойств слов, то есть свойств, которые зависят лишь от количества вхождений каждой из букв в слово, а не от их порядка (см., например, обзор [5]). Многие классические свойства слов имеют абелевы аналоги. Например, слово и называется квадратом, если оно является конкатинацией двух одинаковых слов: и = xx. Естественным образом можно определить абелевы квадраты — слова и = xy, где x и у абелево эквивалентны, то есть состоят из одних тех букв, с учетом кратности. Классический результат Туэ, 1906, говорит, что над трехбуквенным алфавитом существует слово, избегающее квадратов. Изучение абелевых свойств началось с вопроса, заданного П. Эрдешем [4], о существовании слова, избегающего абелевых квадратов. Такое слово над алфавитом минимальной мощности — четырехбуквенным — было впервые построено В. Кера- неном [7]. С тех пор по тематике абелевой избегаемости получено множество разных результатов; например, слова, избегающие длинных абелевых квадратов и кубов, изучаются в статье [13] (см. также ссылки для других результатов по тематике).
Другое классическое свойство слов — периодичность — тоже имеет абелеву версию: слово и называется абелево периодичным, если оно разбивается на блоки, которые абелево эквивалентны между собой. Понятие абелевой эквивалентности имеет ряд модификаций. В этой работе рассматривается слабая абелева периодичность: теперь мы требуем, чтобы слово разбивалось на блоки, в которых частоты букв совпадают, однако длины блоков могут быть разными. Это понятие было введено в [1], где описаны общие свойства слабой абелевой периодичности. Также изучалось избегание степеней в слабом абелевом смысле. В статье [6] описано тернарное бесконечное слово, избегающее слабых абелевых степеней, состоящих из 511 + 1 блоков, а в статье [8] количество блоков улучшено до 189.
Один из самых важных классов слов является класс морфических слов. Рассмотрим отображение, сопоставляющее каждой букве алфавита некоторое слово, тогда его можно доопределить на любом слове и задать морфизм на множестве всех слов. Морфическим словом называется неподвижная точка некоторого морфизма, то есть такое бесконечное слово, которое при применении морфизма не изменяется. В большинстве конструктивных результатов, упомянутых выше, построенные примеры являются морфическими словами. Отметим, что в литературе для этого класса также встречается название чисто морфическое слово, в то время как морфическими иногда называют несколько более широкий класс слов.
Одним из результатов этой работы является критерий слабой абелевой периодичности для бинарных морфических слов. Показано, что свойство слабой абелевой периодичности бинарных морфических слов зависит от собственных чисел матрицы морфизма. А именно, если большее из них иррациональное, то слово не является слабо абелево периодическим, если же большее рациональное, а меньшее не больше единицы, то слово является слабо абелево периодическим, иначе выполнение свойства зависит от структуры морфизма (см. теорему 1).
Другим рассматриваемым абелевым свойством является свойство WELLDOC, которое заключается в следующем. Рассмотрим для каждого фактора и бесконечного слова w и для каждого натурального числа m множество всех префиксов, которые заканчиваются вхождением и. Для выполнения условия WELLDOC требуется, чтобы для каждого вектора длины, равной размеру алфавита, из остатков по модулю m существовал префикс из этого множества такой, что с этим вектором остатков совпадает вектор остатков числа вхождений каждой буквы в этот префикс. В статье [2] это свойство используется для генерации псевдослучайных последовательностей, обладающих хорошими свойствами. Кроме того, доказывается выполнение свойства WELLDOC для слов Арно-Рози и, в частности, слов Штурма. В бакалаврском дипломе автора приводится критерий выполнения свойства WELLDOC для морфических слов, порожденных примитивными морфизмами. В этой работе мы обобщаем этот критерий на все морфические слова. Ключевым моментом в обобщении было доказательство того, что условие равенства определителя матрицы морфизма ±1 является необходимым условием выполнения свойства WELLDOC.
В следующем разделе будут приведены необходимые комбинаторные определения, а также формулировки всех основных результатов этой работы. Необходимые факты из алгебры приводятся в разделе 3. В разделе 4 мы приводим критерий слабой абелевой периодичности для бинарных морфических слов. В бакалаврском дипломе автора был доказан критерий свойства WELLDOC только для примитивных слов. В разделе 5 приведено доказательство недостающей части этого критерия, завершающее критерий для всех морфических слов, в том числе непримитивных.

Купить

В дипломной работе были рассмотрены две задачи об абелевых свойствах морфических слов. Во-первых, был получен критерий слабой абелевой периодичности для бинарных морфических слов. Во-вторых, было получено обобщение характеризации морфических слов, обладающих свойством WELLDOC, с примитивных морфизмов на все морфизмы. Вопрос о характеризации слабой абелевой периодичности для небинарных морфических слов остается открытым.

Купить