RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive

Intelligent systems. Theory and applications, 2023 Volume 27, Issue 2, Pages 68–76 (Mi ista509)

Part 2. Special Issues in Intellectual Systems Theory

On the complexity of converting to a correct linear form

P. S. Dergacha, D. A. Saltsovab

a Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Branch of the Moscow State University named after M.V. Lomonosov in the city of Tashkent

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.



© Steklov Math. Inst. of RAS, 2024