On the complexity of converting to a correct linear form

Dergach Peter Sergeevich; Saltsova Diana Alexandrovna

On the complexity of converting to a correct linear form

Dergach P. S., Saltsova D. A.

Dergach Peter Sergeevich

Ph.D., junior researcher, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Saltsova Diana Alexandrovna

Graduate of the M. V. Lomonosov Moscow State University Branch in Tashkent

Published: 2023, vol. 27, issue 2, pp. 68–78

Download full text (In Russian)

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\), in which the words \(\beta^*_i\) are commensurable.

Keywords: regular language, growth function, regular linear form, complexity.

BibTeX

@article{IS-Dergach-Saltsova2023,
  author  = {Dergach, Peter Sergeevich and Saltsova, Diana Alexandrovna},
  title   = {{On the complexity of converting to a correct linear form}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2023},
  volume  = {27},
  number  = {2},
  pages   = {68--78},
}

AMSBIB

\Bibitem{IS-Dergach-Saltsova2023}
\by P.\,S.~Dergach, D.\,A.~Saltsova
\paper On the complexity of converting to a correct linear form
\jour Intelligent Systems. Theory and Applications
\yr 2023
\vol 27
\issue 2
\pages 68--78
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue