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

Proyecto: Award Project

Detalles del proyecto

Description

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

GRNTI

  • 27.45.15

Type of Financial Sources

  • RNF

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

  • Kuibyshev Research Division

Huella digital

Explore los temas de investigación que se abordan en este proyecto. Estas etiquetas se generan con base en las adjudicaciones/concesiones subyacentes. Juntos, forma una huella digital única.
  • Transition property for cube-free words

    Petrova, E. A. & Shur, A. M., 1 ene 2019, Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. Kucherov, G. & van Bevern, R. (eds.). Springer Verlag, Vol. 11532. p. 311-324 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11532 LNCS).

    Resultado de la investigación: Conference contributionrevisión exhaustiva

    4 Citas (Scopus)