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

Проект: Проект-Грант

Сведения о проекте

Описание

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

Тип источника финансирования (РФФИ, РНФ, Х/Д, Гранты и т.д.)

  • РНФ

ГРНТИ

  • 27.45.15 Общая теория комбинаторного анализа

Площадка НИЧ УрФУ, где ведется данный грант (НИЧ Куйбышева, НИЧ Мира)

  • НИЧ Куйбышева