Nondeterministic state complexity of square root
This closes a long-standing gap in automata theory for a fundamental operation on regular languages.
The paper resolves the nondeterministic state complexity of the square-root operation on regular languages, proving that n³ states are both sufficient and necessary in the worst case for an n-state NFA.
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). In this paper, we close this gap completely and prove that $n^{3}$ states are sufficient and necessary in the worst case.