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

Исследование бесповторных языков - одна из центральных тем в комбинаторике слов с её зарождения в начале XX века по настоящие дни. Важнейшей задачей в изучении бесповторных языков является изучение границы повторяемости и построение бесконечных слов с минимальной избегаемой экспонентой. И если обычные бесповторные языки в этом отношении изучены достаточно хорошо, то в случае абелево бесповторных языков точные значения границы повторяемости неизвестны ни для одного алфавита, а также на данный момент не существует конструкций, позволяющих строить бесконечные слова с избегаемой экспонентой, близкой к предполагаемой границе повторяемости. Это связано с более сложным устройством данных языков и большей сложностью алгоритмов, необходимых для их исследования. Любые результаты по данным задачам внесут существенный вклад в изучение структуры абелево бесповторных языков.
Бесповторным языком называется язык, состоящий из слов, не содержащих (избегающих) некоторую фиксированную степень (экспоненту). Напомним, что слово u^n=u ... u (n раз) есть n-я степень слова u. Рассматривается также понятие дробной степени: пусть слово u имеет длину n, возьмём префикс длины m бесконечного слова v = uuu... и получим слово с экспонентой m/n. Слово называется k-свободным, если оно не содержит подслов с экспонентой >= k и k+-свободным, если оно не содержит подслов с экспонентой > k. Дробные степени позволяют ввести понятие границы повторяемости - это функция RT(n) = inf{k | существует бесконечное k-свободное слово над n-буквенным алфавитом}.
Понятие степени слова имеет несколько обобщений, одно из которых - абелева степень. Мы говорим, что слово u есть абелева степень слова w, если u представимо в виде произведения слов, каждое из которых является некоторой перестановкой букв слова w. Например, слово abcbac - абелев квадрат. Язык или слово, избегающий абелеву степень k, также называется абелево k-свободным, будем называть их А-k-свободными. Абелевы степени будем называть А-степенями. Целые А-степени могут быть обобщены до дробных несколькими способами. В случае степени меньше 2 предпочтительно следующее определение благодаря симметрии. Слово vuv' называется (m/n)-А-степенью слова vu, если |vu|=n,|vuv'|=m и v' является перестановкой v. Определив понятие дробной А-степени, мы можем ввести понятие абелевой границы повторяемости ART(n) = inf{k | существует бесконечное абелево k-свободное слово над n-буквенным алфавитом}. В статье (Samsonov, AV, Shur, AM: On Abelian repetition threshold. RAIRO Theor. Inf.Appl.46, 147–163 (2012)) выдвинута гипотеза о том, что абелева граница повторяемости устроена следующим образом:
ART(2)=11/3;
ART(3)=2;
ART(4)=9/5;
ART(k)=(k-2)(k-3) для k > 4.
Автором проекта разработаны алгоритмы поиска в абелево бесповторных языках, с помощью которых было получено и обработано большое количество экспериментальных данных. Это позволило выдвинуть новую гипотезу об абелевой границе повторяемости:
ART(2)>11/3;
2ART(4)>9/5;
ART(5)=3/2;
4/3ART(k)=(k-3)(k-4) для k > 6.
Основной задачей данного проекта является работа над данной гипотезой: доказательство или улучшение представленных оценок для ART(k), в первую очередь, для 5- и 6-буквенного алфавита, поскольку для них представляется возможным найти точные оценки с помощью разработанных алгоритмов. Для алфавитов большей мощности требуются другие подходы, доказательство оценок с помощью оптимизированного перебора невозможно. Для данных алфавитов построенные случайные пути демонстрируют явный "фазовый переход" в точке (k-3)/(k-4): А-(k-3)/(k-4)-свободные языки ведут себя как конечные, а А-((k-3)/(k-4))+-свободные -- как бесконечные. Для работы над гипотезой об абелевой границе повторяемости требуются конструкции, порождающие бесконечные А-свободные слова, поскольку существующие на данный момент конструкции не годятся для слов, избегающих дробные экспоненты. В данном проекте планируется разработка таких конструкций двумя методами:
1) генерация морфизмов на основе полученных статистических данных в ходе вычислительных экспериментов на основе описанных выше алгоритмов;
2) построение слов на основе слов Тёплица .
Ожидаемые результаты
1. Получение точного значения либо улучшение существующих оценок для абелевой границы повторяемости над одним или несколькими алфавитами
2. Разработка конструкции для построения бесконечных абелево бесповторных слов над маленькими алфавитами с экспонентой меньше 2.
Решение данных задач даст существенный сдвиг в изучении абелевой границы повторяемости и структуры абелево бесповторных языков в целом. Все планируемые результаты соответствуют мировому уровню в данной дисциплине.