Рекуррентность и равномерная рекуррентность бесконечных слов и их произведений

• Автор: Салимов, Павел Вадимович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 77 с.

Оглавление
Введение
1 Определения и предварительные сведения
1.1 Множество слов
1.2 Морфизмы
1.3 Морфизмы и циркулярность
1.4 Слова Теплица
1.5 Обобщенные вращательные слова
2 Равномерная рекуррентность произведений слов
2.1 Класс сильно рекуррентных бесконечных слов
2.2 Слова типа Туэ-Морса
2.3 Обобщенно вращательные слова
2.4 Слова Теплица
3 Графовые структуры на языках
3.1 Графы Рози, растяжения и графы перекрытия путей
3.2 Вложимость растяжений в графы де Брейна
3.3 Вложимость растяжений графов де Брейна
3.4 Конструирование языков
4 Сложностные функции бесконечных слов
4.1 Арифметическая и максимальная шаблонная сложности .
4.2 Конструирование слов промежуточной арифметической сложности

4.3 Максимальная шаблонная сложность некоторых автоматных слов
Литература

Введение
Цели и результаты работы
В диссертации изучаются свойства бесконечных слов - последовательностей элементов конечного множества, называемого алфавитом. Формально, бесконечное слово х над алфавитом Е есть отображение 1М0 —> Е, где Ето - множество натуральных чисел с нулем.
Следуя историческому пути развития математики, сформулируем основной изучаемый в работе вопрос в общих топологических терминах.
Центральное понятие работы, равномерная рекуррентность, является одним из фундаментальных понятий теории динамических систем. Определим динамическую систему как пару {Х,Т), где X есть топологическое пространство с заданным на нем непрерывным отображением Т : X —> X. Это определение, более узкое по сравнению со стандартным, вполне достаточно для объяснения постановки изучаемых в данной работе вопросов и полученных результатов. Траекторией точки х назовем последовательность точек х,Тх, Т2х,.... Определим множество возвращения В{х, II) точки х в ее окрестность и а X как множество таких п 6 ИЧ0, что Тпх £ и. Точку х называют периодичной, если ее траектория периодична: для некоторого т выполнено Ттх = х .
Теория динамических систем начинается с работ Пуанкаре, посвященных механике. В них он отступил от привычного вопроса о выяснении свойств траектории отдельно взятой точки в сторону изучения свойств совокупности траекторий всех точек в целом. Так, одним из первых ре-

Следствие 1. Блочное представление слова равномерно рекуррентно тогда и только тогда, когда само слово равномерно рекуррентно.
Доказательство. (<£=) Пусть слово х — х$х... равномерно рекуррентно, и т. > 0 есть произвольное число. Рассмотрим такое слово х! =
... над алфавитом Е, что х = х^х^^... ад+т_1. Очевидно, что слово х' равномерно рекуррентно, причем Бх'{п) ^ 7?,ж(п + то — 1). Заметим, что блочное представление х1П11 = х'йх'тх'2тп ■ ■ ■ является арифметической подпоследовательностью слова х' и, следовательно, равномерно рекуррентно по Лемме 12.
(=>) Пусть для некоторого числа тп > 0 блочное представление тт слова х равномерно рекуррентно. Заметим, что слово х получается из слова т;['т1 применением очевидного морфизма. Следовательно, по Лемме 3, х равномерно рекуррентно. □
Используя Следствие 1 мы можем обогатить класс 57? периодичными словами.
Лемма 13. Класс 57? включает все периодичные слова.
ДОКАЗАТЕЛЬСТВО. Пусть слово х периодично с периодом тп, а у есть произвольное равномерно рекуррентное слово. Заметим, что (ж <£> у)^ равномерно рекуррентно, т.к. (х®у)^ ~ х^ 0у^, где х^ - константное слово. Отсюда, но Следствию 1 Леммы 12, следует равномерная рекуррентность слова х ® у. □
Докажем еще несколько свойство класса 57?.
Утверждение 13. Класс 57? замкнут относительно операции взятия арифметических подпоследовательностей.
Доказательство. Пусть слово х принадлежит классу 57?, а слово у равномерно рекуррентно. Для произвольных чисел к > 0 и д ^ 1 докажем, что А^^х ® у равномерно рекуррентно.