Abstract:
This paper is devoted to the study of the regular linear form for regular languages with polynomial growth function and improving the corresponding estimates on the complexity of the transition from the linear form to the regular linear form.
We managed to lower the previously known estimate $ n^2 $ from [1] to an estimate $ \frac{n^2}{2} + n $. Also obtained an upper estimate $ \frac{n^2}{4} $ for languages of the form $ \beta^*_1 \beta^*_2 ... \beta^*_s $.
Keywords:regular language, growth function, regular linear form, complexity.