Комбинаторные сложностные характеристики слов Штурма

В статье рассматриваются комбинаторные сложностные характеристики бесконечных слов, а именно комбинаторная сложность и ее модификации. Прежде всего, представлен обзор имеющихся результатов для класса слов с наименьшей комбинаторной сложностью - слов Штурма. Особое внимание уделено арифметической сложности бесконечных слов, начало изучение которой положила Теорема Ван дер Вардена об одноцветных арифметических прогрессиях. Арифметическая сложность является в некотором смысле модификацией комбинаторной сложности. Представлен обзор текущих результатов и точных значений арифметической сложности для слов Штурма. В статье представлена полиномиальная Теорема Ван дер Вардена, дающая начало изучению более обобщенной модификации функции комбинаторной сложности - полиномиальной сложности бесконечных слов. В завершение, мы представляем ряд открытых проблем для дальнейшего исследования.