Nondeterministic state complexity of square root

Sergey Onishchenko

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 auto…