Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Nondeterministic state complexity of square root

Abstract

We investigate the nondeterministic state complexity of the square-root operation \(\sqrt {L}=\{\,w \mid ww\in L\,\}\) on regular languages represented by nondeterministic finite automata. For an \(n\)-state NFA accepting \(L\), it was previously known that \(\sqrt {L}\) can be accepted by an NFA with at most \(n^{3}\) states, while the best lower bound, was only \((n-1)(n-2)(n-3)\). We are going to close this gap completely and prove that \(n^{3}\) states are sufficient and necessary in the worst case.

Keywords: state complexity, language operations, nondeterministic finite automata.

BibTeX
@article{IS-Onishchenko2026,
  author  = {Onishchenko, Sergey},
  title   = {{Nondeterministic state complexity of square root}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {121--122},
}
AMSBIB
\Bibitem{IS-Onishchenko2026}
\by S.~Onishchenko
\paper Nondeterministic state complexity of square root
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 121--122
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover