Кирова Валерия Орлановна
«Комбинаторные сложностные характеристики бесконечных слов»
Описание курса:
Курс включает основы комбинаторики слов и отвечает на вопросы: какими свойствами может и не может обладать множество подслов данного слова? Сколько заданным образом фрагментов определённого размера может содержаться в бесконечном слове? Как меняется их количество? В рамках курса будет представлен полный обзор имеющихся функций сложности бесконечных слов, которых более десятка: сложность Ли, Абелева сложность, k-абелева сложность, максимальная шаблонная сложность, сложность цикла, биномиальная сложность, оконная сложность, периодическая сложность, полиномиальная сложность. Для ряда функций будет представлен перечень открытых исследовательских задач.
План курса:
Лекция 1. Комбинаторика символьных последовательностей. Введение, предварительные сведения, основные определения.
Лекция 2. Периодические слова. Свойство взаимодействия периодов. Вращательные слова. Равномерно рекуррентные слова. Факторные языки и операции над ними. Моноид факторных языков. Канонические разложения.
Лекция 3. Некоторые классы бесконечных слов.
Лекция 4. Морфизм слов. Задание бесконечных слов морфизмами.
Лекция 5. Избегаемость слов и паттернов.
Лекция 6. Комбинаторная сложность.
Лекция 7. Связки и стирания. Теорема Бина-Эренфойхта-Макналти-Зимина.
Лекция 8. Слова Штурма: эквивалентные определения через вращения, сбалансированные слова, механические слова, морфизмы и стандартные слова.
Лекция 9. Геометрический двойственный метод. Доказательство комбинаторной сложности слов Штурма через геометрический двойственный метод.
Лекция 10. Периодичность и сложность бесконечных перестановок: бесконечные перестановки и бесконечные слова, периодические бесконечные перестановки, периоды конечных перестановок.
Лекция 11. Модификации комбинаторной сложности: арифметическая, полиномиальная сложность.
Лекция 12. Максимальная шаблонная сложность перестановок. Автоматные перестановки. Факторы и факторная сложность.
Лекция 13. Различные подходы к сложности слов: шаблонная, абелева сложность, k-абелева сложность, оконная сложность.
Лекция 14. Различные подходы к сложности слов: максимальная шаблонная сложность, сложность цикла.
Лекция 15. Различные подходы к сложности слов: биномиальная сложность, периодическая сложность, сложность Ли.
