Description

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

    Type of Financial Sources

  • RNF

    GRNTI

  • 27.45.15

    UrFU Research Division section that handles this grant (Kuibyshev, Mira)

  • Kuibyshev Research Division

ID: 9124468