КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ


Номер 18-71-00043

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

РуководительПетрова Елена Александровна, Кандидат физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Уральский федеральный университет имени первого Президента России Б.Н. Ельцина", Свердловская обл

Период выполнения при поддержке РНФ 07.2018 - 06.2020 

Конкурс№29 - Конкурс 2018 года по мероприятию «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными.

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-114 - Дискретная математика и математическая кибернетика

Ключевые словакомбинаторика слов, бесповторные языки, префиксные деревья, продолжаемые слова

Код ГРНТИ27.47.00


СтатусУспешно завершен


 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ


Аннотация
Данный проект нацелен на решение ряда связанных друг с другом задач о внутренней структуре бесповторных языков. Исследование бесповторных языков - одна из центральных задач комбинаторики слов, сохраняющая свою актуальность на протяжении последнего столетия. Множество результатов было получено в этой области со времён Акселя Туэ, основателя данной дисциплины, однако по-прежнему остаётся открытым множество проблем. Изучение внутренней структуры частично упорядоченных множеств, образованных словами бесповторного языка относительно таких естественных порядков как префиксный или суффиксный, очень важно для понимания внутреннего устройства такого языка. Эта задача имеет связь с такими важными аспектами как положение слова в языке (полугрупповой аспект) и комбинаторная сложность языка. На данный момент с этой стороны хорошо изучен бинарный сильно-бескубный язык, но о языках, изучаемых в данном проекте (бинарный бескубный и тернарный бесквадратный) известно немного ввиду их более сложного устройства. В рамках проекта планируется получить результат о логарифмическом размере конечного поддерева, порождённого произвольным словом в данных языках, который является существенным улучшением существующего результата, дающего лишь субполиномиальную оценку, а также решить проблему о соединении двух бесконечно продолжаемых вправо и влево слов, сформулированную в статье Рестиво и Салеми 1985 года и решённую пока только для бинарного сильно-бескубного языка. Все планируемые результаты несомненно будут обладать научной новизной.

Ожидаемые результаты
Доказательство логарифмической от длины слова оценки на количество узлов в порождённом данным словом конечном поддереве в дереве префиксного порядка тернарного бесквадратного и бинарного бескубного языков. Решение проблемы о соединении произвольных продолжаемого вправо и продолжаемого влево слов в тернарном бесквадратном и бинарном бескубном языках. Ожидаемые результаты соответствуют мировому уровню в данной дисциплине.


 

ОТЧЁТНЫЕ МАТЕРИАЛЫ


Аннотация результатов, полученных в 2018 году
Основной целью данного проекта является решение задачи, сформулированной Рестиво и Салеми (A. Restivo, S. Salemi, Some decisions results on nonrepetitive words, Combinatorial Algorithms on Words, Springer-Verlag (1985), pp. 289--295), о соединении двух продолжаемых бесповторных слов для важных случаев бесповторных языков --- бинарного бескубного и тернарного бесквадратного. Напомним, что бесповторными называются слова, не содержащие в себе повторов, т.е. степеней некторого слова. Например, слова, не содержащие двух идущих подряд одинаковых фрагментов, называются бесквадратными. Существует ряд задач, играющих вспомогательную роль в этом вопросе. В частности, это задачи о доказательстве логарифмической оценки конечного поддерева, порождённого словом в дереве префиксного порядка, которые планировалось решить в первый год выполнения работ по гранту. Фактически в первый год выполнения проекта осуществлена работа по решению основной задачи для бинарного бескубного языка (задача 4 конкурсной заявки, причём не просто для бинарного бескубного языка, а для бескубных языков над любым конечным алфавитом; кроме того, данная задача решена конструктивно, т.е. не просто доказано существование соединяющего слова для двух продолжаемых слов, а разработан алгоритм построения данного слова), что является более важным результатом, нежели решение задачи о логарифмической оценке поддерева, запланированное изначально на первый год. Решение этой задачи в будущем позволит улучшить алгоритм, предложенный в работе по решению задачи 4. В ходе работы задача о соединяющем слове для произвольных продолжаемых бинарных бескубных слов была сведена к поиску соединяющего слова для так называемых равномерных слов. Слово называется раавномерным, если оно может быть разбито на блоки ab и ba за исключением, возможно, первой и/или последней буквы. Например, слово abaababb является равномерным. В данной работе доказано утверждение о том, что если равномерное слово продолжаемо на 3 символа, то оно, во-первых, бесконечно продолжаемо, во-вторых, среди его правых контекстов (продолжений) есть некоторый суффикс слова Туэ-Морса. В данной работе доказано, что для любых слов u и v, где u --- бесконечно продолжаемое вправо и имеющее среди своих правых контекстов u't_1, v --- бесконечно продолжаемое слово и имеющее среди своих левых контекстов t_2v' (t_1, t_2 --- подслова слова Туэ-Морса), существует соединяющее слово w, причём оно само является подсловом Туэ-Морса. Основная по объёму и сложности подзадача, которая была решена, --- доказать, что у бесконечно продолжаемого слова существует контекст с конечным числом маркеров --- минимальных подслов, <<нарушающих>> равномерность. В нашем случае маркерами являются слова aabaa, bbabb, aababaa, bbababb. Данная теорема доказывается от противного --- требуется показать, что у слова u все бесконечные контексты не могут содержать бесконечное число маркеров. Это делается путём построения ограничения на длину такого контекста в зависимости от |u|. Эту технику удалось перенести и на случай произвольного алфавита. Чтобы решить задачу о соединяющем слове для бескубных слов над произвольным алфавитом, достаточно доказать, что продолжаемое слово имеет среди своих бесконечных контекстов такой, который заканчивается на бесконечное бинарное слово. Финальной работой по решению задач о соединяющем слове для бескубных слов является разработка алгоритмов построения бинарных контекстов и соединяющего слова для двух продолжаемых слов. По вышеизложенным результатам подготовлен и сделан доклад на международном семинаре Ural Workshop on Group Theory and Combinatorics, прошедшем с 22 по 24 марта 2019 года в Уральском федеральном университете. Задача о соединяющем слове для случая тернарного бесквадратного языка (задача 2 из конкурсной заявки) находится в работе. Предполагается применить к ней технику, подобную использованной для случая бескубных бинарных слов, т.е. сведение к соединению равномерных слов бесконечного слова с наименьшей из возможных избегаемых степеней. Для тернарного бесквадратного языка таким словом является, например, слово Аршона, которое не содержит подслов степени больше 7/4. Равномерными в данном случае являются слова, которые можно разбить на блоки вида abc, bca, cab, acb, bac, cba. В ходе работ по проекту доказано, что равномерные продолжаемые слова имеют среди своих контекстов слова вида vt, где t --- некоторый суффикс слова Аршона. Для тернарных бесквадратных слов удобно использовать их представление в виде маршрутных кодов. Получено описание маршрутных кодов равномерных слов. Ведётся работа над доказательством о существовании контекста с конечным числом маркеров (в данном случае маркерами служат определённые маршрутные коды), однако она ещё не завершена ввиду того, что тернарный бесквадратный язык имеет более сложное устройство, нежели бинарный бескубный. Доработана задача о частоте ветвления префиксного дерева бинарных бескубных слов (первые результаты опубликованы в Petrova E.A., Shur A.M., On the tree of binary cube-free words , Proc 21st Internat., Conf. DLT 2017. - Vol. 10396 of LNCS .- 2017. - P. 296-307). Использована техника приближения бесповторных языков регулярными языками (разработана А.М. Шуром в A. M. Shur. Growth rates of complexity of power-free languages. Theoret. Comput. Sci., 411:3209-3223, 2010.), а также алгоритм Карпа поиска цикла минимальной стоимости в графе (Richard M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23(3):309-311, 1978.). С помощью различных оптимизаций удалось произвести расчёты на конечном автомате для бинарного языка, избегающего кубы с периодом до 18 включительно, что позволило улучшить предыдущие результаты и получить новые. В итоге, получена лучшая по сравнению с предыдущим результатом нижняя оценка на частоту ветвления (0.38125), построен путь, имеющий частоту ветвления ниже индекса роста языка бинарных бескубных слов (0.44828), получена верхняя оценка на частоту ветвления (0.72043), построен путь, имеющий частоту ветвления, очень близкую к верхней оценке (0.72). Данные результаты могут быть использованы для решения задачи о логарифмической оценке размера поддерева, порождённого словом в префиксном дереве бинарного бескубного языка (задача 3 конкурсной заявки). Данные результаты оформлены в виде статьи, отправленной на рассмотрение в журнал Electronic Journal of Combinatorics.

 

Публикации

1. Петрова Е.А., Шур А.М. Transition Property for Cube-Free Words Lecture Notes in Computer Science, - (год публикации - 2019)


Аннотация результатов, полученных в 2019 году
Основной целью данного проекта является решение задачи, сформулированной Рестиво и Салеми (A. Restivo, S. Salemi, Some decisions results on nonrepetitive words, Combinatorial Algorithms on Words, Springer-Verlag (1985), pp. 289--295), о соединении двух продолжаемых бесповторных слов для важных случаев бесповторных языков - бинарного бескубного и тернарного бесквадратного. Напомним, что бесповторными называются слова, не содержащие в себе повторов, т.е. степеней некторого слова. Например, слова, не содержащие двух идущих подряд одинаковых фрагментов, называются бесквадратными. Существует ряд задач, играющих вспомогательную роль в этом вопросе. В частности, это задачи о доказательстве логарифмической оценки конечного поддерева, порождённого словом в дереве префиксного порядка. В ходе работы над задачей о соединяющем слове для произвольных продолжаемых тернарных бесквадратных слов были сделаны попытки решить её, основываясь на технике, успешно применённой к аналогу этой задачи для бинарных бескубных слов. А именно, свести её к задаче о соединяющем слове для так называемых равномерных слов. Слово называется равномерным, если оно может быть разбито на блоки abс, acb, bac, bca, cab, cba исключением, возможно, двух первых и/или их букв. Доказано утверждение о том, что если равномерное слово продолжаемо на несколько символов, то оно, во-первых, бесконечно продолжаемо, во-вторых, среди его правых контекстов (продолжений) есть некоторый суффикс слова Аршона (бесконечное слово с минимальной для тернарного алфавита экспонентой, которое предполагается использовать в качестве основной части соединяющего слова). Тернарные бесквадратные слова рассматриваются здесь как маршрутные коды - пути в помеченном графе K3,3. Получено описание маршрутных кодов равномерных слов, а также "маркеров" - минимальных по включению слов, нарушающих равномерность. В случае тернарного бесквадратного языка доказать, что у продолжаемого слова не может быть контекста с бесконечным числом маркеров (ими в данном случае являются определённые маршрутные коды) оказалось гораздо более сложной задачей, которая пока не решена. Доказано, что соединяющее слово существует для любых двух продолжаемых равномерных слов, а также для продолжаемых слов, содержащих уникальную последовательность маркеров или уникальное равномерное подслово. Среди разработанных техник нужно отметить быстрый алгоритм, который по данному произвольному бесквадратному слову определяет, какие из суффиксов бесконечного слова Аршона являются его продолжениями. Для задачи о логарифмической оценке на размер конечного поддерева, порождённого словом в дереве префиксного порядка тернарного бесквадратного языка, разработан алгоритм, который по заданному поддереву строит минимальное по длине слово, его порождающее. Доказаны важные утверждения о свойствах взаимодействия периодов в дереве тернарных бесквадратных слов, а также получены улучшенные результаты о частоте ветвления префиксного дерева тернарных бесквадратных слов (первые результаты опубликованы в (E. A. Petrova and A. M. Shur. On the tree of ternary square-free words. In Combinatorics on Words - 10th Internat. Conf. WORDS 2015, Proceedings, volume 9304 of LNCS, pages 223–236. Springer (2015)). Использована техника приближения бесповторных языков регулярными языками (разработана А.М. Шуром в A. M. Shur. Growth rates of complexity of power-free languages. Theoret. Comput. Sci., 411:3209-3223, 2010.) С помощью различных оптимизаций удалось произвести расчёты на конечном автомате для языка тернарных слов, избегающего квадраты с периодом до 24 включительно, что позволило улучшить предыдущие результаты. В итоге получена лучшая по сравнению с предыдущим результатом нижняя оценка на частоту ветвления (0.25).

 

Публикации

1. Петрова Е.А., Шур А.М. Transition Property for Cube-Free Words Theory of Computing Systems, - (год публикации - 2020) https://doi.org/10.1007/s00224-020-09979-4


Возможность практического использования результатов
не указано