Информация по курсу

Содержание курса

Раздел 1 Уравнения над словами, периоды конечных слов
1. Слова и языки. Конкатенация. Уравнения над словами. Уравнение XY=YX. Примитивные слова.
2. Периоды слова. Экспонента слова. Лексикографический порядок. Слова Линдона.
3. Теорема Файна-Вильфа. Точность оценки.
4. Локальный период слова в точке. Теорема о критическом разбиении.

Раздел 2 Избегаемость слов и паттернов
1. Морфизмы. Задание бесконечных слов морфизмами. Слово Туэ-Морса. Слова Теплица.
2. Избегаемость слов и паттернов. Избегаемые экспоненты.
3. Теорема Туэ о 2-избегаемости экспоненты 2+. Слова Аршона. 3-избегаемость экспоненты (74)+.
4. Гипотеза Дежан. Доказательство нижней оценки. Кодировка Пансьё. Типы повторов.
5. Неизбежные шаблоны. Слова Зимина, их свойства. Теорема Бина-Эренфойхта-Макналти-Зимина.

Раздел 3 Сложность бесконечных слов, слова Штурма
1. Комбинаторная сложность языков и бесконечных слов. Теорема Морса-Хэдлунда о связи сложности
и периодичности. Гипотеза Нива. Сложность слов Фибоначчи и Туэ-Морса.
2. Слова Штурма эквивалентные определения через вращения, сбалансированные слова, морфизмы и стандартные слова.
3. Разложение в непрерывную дробь. Связь с диофантовыми приближениями. Количество всех слов Штурма.
4. Эпиштурмовы слова и слова Арно-Рози.
5. Теорема классификации сложности бесконечных слов, порожденных морфизмами.
6. Различные подходы к сложности слов шаблонная, абелева сложность.

Лекторы