EN
О сложности перехода к правильному линейному виду
Опубликована: 2023 год, том 27, выпуск 2, С. 68–78
Аннотация
Данная работа посвящена изучению правильного линейного вида для регулярных языков с полиномиальной функцией роста и улучшению соответствующих оценок на сложность перехода от линейного вида к правильному линейному виду. Удалось понизить ранее известную из работы [1] оценку \(n^2\) до оценки \(\frac{n^2}{2} + n\). Так же получена верхняя оценка \(\frac{n^2}{4}\) для языков вида \(\beta^*_1 \beta^*_2 ... \beta^*_s\), в которых слова \(\beta^*_i\) соизмеримы.
Ключевые слова: регулярный язык, функция роста, правильный линейный вид, сложность.
BibTeX
@article{IS-Dergach-Saltsova2023,
author = {Дергач, Пётр Сергеевич and Сальцова, Диана Александровна},
title = {{О сложности перехода к правильному линейному виду}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2023},
volume = {27},
number = {2},
pages = {68--78},
}
AMSBIB
\RBibitem{IS-Dergach-Saltsova2023}
\by П.\,С.~Дергач, Д.\,А.~Сальцова
\paper О сложности перехода к правильному линейному виду
\jour Интеллектуальные системы. Теория и приложения
\yr 2023
\vol 27
\issue 2
\pages 68--78
Опубликовано на условиях лицензии
Creative Commons Attribution 4.0 International (CC BY 4.0)