Общей целью проекта является решение нескольких важных задач комбинаторики слов, а также междисциплинарных задач на стыке с динамическими системами и формальными языками. Получен ряд результатов в комбинаторике слов, а также решено несколько междисциплинарных задач на стыке с динамическими системами и формальными языками. В частности, руководителем проекта изучена низкая абелева сложность двумерных слов и получен абелев аналог гипотезы Нива, исследованы k-абелевы палиндромы в бесконечных словах (совместно с Ю. Кархумяки и Ж. Кассенем); введено и исследовано новое понятие абелевого замыкания орбиты бесконечного слова (совместно с М. Вайтлендом и Ю. Кархумяки); изучены абелево насыщенные слова (cовместно с С. Августиновичем, Ю. Кархумяки, Ж. Кассенем, А. Саарелой); законечено исследование иерархии бесконечных слов в терминах факторизации подслов (совместно с А. Фрид, Ж. Кассенем и Л. Замбони), в частности, получена характеризация слов линейной сложности; исследована равномерная рекуррентность двумерных слов по направлениям (совместно с Э. Вандом и Э. Шарлье); исполнителем проекта (совместно с А. Охотиным, Санкт-Петербург) изучены свойства линейных грамматик, в том числе доказано, что всякую линейную LL(k)-грамматику можно преобразовать к линейной LL(1)-грамматике. Опубликовано пять статей в международных журналах и четыре статьи в рецензируемых трудах международных конференций.

Все результаты, запланированные в проекте, выполнены; опубликовано 5 статей в международных журналах и 4 статьи в рецензируемых трудах международных конференций, индексируемых всеми основными базами (журналы Information and Computation, Theoretical Computer Science, Proceedings of AMS, Proceedings of French Mathematical Society, Electronic journal of Combinatorics и серия Lecture Notes in Computer Science). Результаты доложены на шести международных конференциях и нескольких научных докладах в университетах за рубежом.

Одним из направлений проекта является изучение абелевых свойств слов. Конечные слова u и v называются абелево эквивалентными, если каждая буква встречается одинаковое число раз в словах u и v. Руководителем проекта (совместно с М. Вайтлендом и Ю. Кархумяки из университета Турку, Финляндия) введено понятие абелева сабшифта A_x бесконечного слова x - это множество таких бесконечных слов y, что для всякого фактора u слова y существует фактор v слова x, который абелево эквивалентен u. Понятие абелевого сабшифта дает характеризацию слов Штурма: среди бинарных равномерно рекуррентных слов слова Штурма - это в точности слова, для которых A_x совпадает с замыканием орбиты Ω_x. С другой стороны, абелев сабшифт слова Туэ-Морса содержит несчетное множество минимальных сабшифтов. Изучено понятие абелевого сабшифта, в частности, охарактеризованы абелевы сабшифты рекуррентных апериодических сбалансированных слов, а также абелевы сабшифты слов минимальной сложности над произвольным конечным алфавитом. Результаты доложены на международных конференциях DLT2018 (Developments in Languages Theory) в Японии и Words 2019 в Великобритании и опубликованы в рецензируемых трудах конференций (LNCS, издается Springer).

Руководителем проекта получен абелев аналог гипотезы Нива и связи между периодичностью и сложностью, и изучена малая абелева сложность двумерных слов. Сложность одномерного бесконечного слова - это функция p(n), которая считает число его различных подслов длины n. Комбинаторная сложность дает некоторую меру "случайности" слова: периодические слова имеют ограниченную комбинаторную сложность, а цифровые представления нормальных чисел - максимальную сложность. В одномерном случае если сложность слова p(n)<=n для некоторого n, то классическая теорема Морса и Хедлунда, 1938, гласит, что слово периодическое. В двумерном случае подобное утверждение известно как гипотеза Нива (Nivat, приглашенный доклад на ICALP 1997), которая утверждает, что если для двумерного слова существуют два натуральных числа n и m такие что сложность p(n,m)<=nm, то слово имеет вектор периодичности. Был найден ряд слабых версий гипотезы, но гипотеза остается недоказанной несмотря на усилия многочисленных ученых. В случае абелевой сложности в одномерных словах классический результат Ковена и Хедлунда говорит, что если для некоторого n абелева сложность слова равна единице, то слово периодическое, но существуют непериоднические слова абелевой сложности два для всякого n, и такие слова - это в точности слова Штурма. В рамках проекта было показано, что ни один из этих результатов не обобщается на двумерный случай: существуют непериодические двумерные слова, сложность которых по некоторым прямоугольникам равна единице. Доказано, что если абелева сложность двумерного слова не более двух, то такое слово периодическое. Этот результат оптимален в том смысле, что существуют апериодические двумерые слова, сложность которых не более трех; более того, значение 3 должно достигаться на бесконечно больших прямоугольниках. Результаты опубликованы в статье в Electronic Journal of Combinatorics.

Следующий полученный результат также касается абелевых свойств слов и палиндромов, т.е. слов, равных своему обращению. Опубликована статья (совместно с Ю. Кархумяки из университета Турку, Финляндия, и Ж. Кассенем из университета Экс-Марселя, Франция), в которой рассматривается k-абелева модификация понятия палиндрома. Два слова называются k-абелево эквивалентными, если они содержает одинаковое число вхождений всякого подслова длины не более k. Говорят, что слово является k-абелевым палиндромом, если оно абелево эквивалентно своему обращению. В статье изучен следующий вопрос: как много различных палиндромов может содержать строка длины n? Известно, что слово длины n может содержать не более, чем n+1 различных палиндромов (в классическом смысле) в качестве подслов; такие слова называются богатыми. С другой стороны, существуют бесконечные слова, содержащие только конечное число различных палиндромов в качестве подслов; такие слова называются бедными. Показано, что в k-абелевом случае существуют бесконечные слова, содержащие конечное число различных k-абелевых палиндромных подслов. Для богатых слов показано, что существуют конечные слова длины n, содержащие \Theta(n^2) различных k-абелевых палиндромов в качестве факторов. Статья опубликована в журнале Information and Computation.

Смежный результат об абелево насыщенных словах - совместная работа с С. В. Августиновичем (ИМ СО РАН, Новосибирск), Ж. Кассенем (Марсель), Ю. Кархумяки и А. Саарелой (Турку). Пусть f: N->R возрастающая функция. Будем говорить, что бесконечное слово w абелево f(n)-насыщенное, если всякий его фактор длины n содержит \Theta(f(n)) абелево неэквивалентных факторов. Показано, что бинарные бесконечные слова не могут быть абелево n^2-насыщенными, но для всякого \epsilon существуют абелево n^(2-\epsilon) насыщенные бинарные слова. Также исследованы связи между абелево насыщенными словами и палиндромной богатостью в случае равенства и k-абелевой эквивалентности. Статья опубликована в журнале Theoretical Computer Science.

Следующая серия результатов - совместная работа с Л. Замбони (университет Лион 1), Ж. Кассенем и А. Фрид (университет Экс-Марселя) - посвящена комбинаторной сложности бесконечных слов и влияния на нее локальных условий. Получена новая характеризация бесконечных слов линейной сложности, а именно, показано, что сложность бесконечного слова линейна если и только если существует язык S ограниченной сложности, такое что всякий фактор w бесконечного слова представляется в виде конкатенации двух элементов S, т.е. w=uv, где u, v∈S. По аналогии со словами, комбинаторная сложность языка L определяется как функция p_L(n), которая считает для всякого n число различных слов в L длины n. Нас интересует следующий вопрос: верно ли, что L содержится в конечном произведении вида S^k, где S - язык сложности, меньшей, чем L? Изучены языки нулевой топологической энтропии, а именно lim sup_{n→∞} log p_L(n)/n = 0. Мы определяем α-размерность языка L как минимум целых чисел k, таких что существует язык S сложности O(n^α), такой что L ⊆ S^k. Стоимостью c(L) языка L называется минимум действительных чисел α, для которых α-размерность языка L конечна. В частности, определения можно использовать для языка всех факторов бесконечного слова. Изучены связи между сложностью языка (или бесконечного слова) и его размерностью и стоимостью, и показано, что эти связи имеют довольно сложную и неочевидную природу. По результатам опубликованы статьи в журналах Proceedings of American Mathematical Society и Bulletin of French Mathematical Society.

Совместно с Э. Вандом (Монреаль/Прага) и Э. Шарлье (Льеж, Бельгия) изучены различные модификации понятия равномерной рекуррентности в многомерных словах. d-мерное бесконечное словао называется равномерно рекуррентным, если для всяких (n_1, . . . , n_d) ∈ \mathbb{N}^d существует N ∈ \mathbb{N}, такое что всякий блок размера (N, . . . , N) содержит префикс размера (n_1, . . . , n_d). Мы ввели новое понятие равномерной рекуррентности многомерных бесконечных слов: для всякого рационального наклона (q_1, . . . , q_d), всякий префикс должен появляться вдоль этого наклона, то есть в позициях i(q_1, . . . , q_d), на ограниченных расстояниях. Такие слова называются равномерно рекуррентными по направлениям. Найдено и исследовано несколько конструкций многомерных слов, удовлетворяющих этому условию, а также рассмотрена серия различных условий на рекуррентность. Изучены общие свойства этих новых понятий, в частности, сильная равномерная рекуррентность неподвижных точек многомерных морфизмов. Полученные результаты доложены на международной конференции LATA2019 и опубликованы в рецензируемых трудах конференции (серия LNCS, издается Springer).

Метод синтаксического анализа LL(k), где k - число просматриваемых следующих символов, широко известен. В частности, ещё на заре этой теории Курки-Суонио (1969) и Розенкранц и Стирнс (1970) показали, что LL(k+1)-анализом можно разобрать строго больший класс языков, чем LL(k)-анализом. Позднее Ибарра и др. (1988) и Хольцер и Ланге (1993) изучали особый случай - линейный LL(k)-анализ - но вопрос о том, ведёт ли увеличение параметра k к расширению применимости алгоритма, оставался неисследованным. Исполнителем проекта (совместно с А. Охотиным, Санкт-Петербург) изучены свойства линейных грамматик, а именно, доказано, что всякую линейную LL(k)-грамматику можно преобразовать к линейной LL(1)-грамматике. Построение ведёт к экспоненциальному росту размера грамматики - и, следовательно, кода синтаксического анализатора. Результат представлен на конференции RuFiDiM 2019 (Russian-Finish Symposium on Discrete Mathematics). В работе "On the transformation of LL(k)-linear grammars to LL(1)-linear" показано, что этот рост в худшем случае неизбежен, и существуют языки, распознаваемые линейным LL(k)-анализатором экспоненциально меньшего размера, чем всякий линейный LL(1)-анализатор для того же языка. Результаты приняты на конференцию Computer Science in Russia, 2020, труды публикуются в серии LNCS, Springer.