Nondeterministic state complexity of square root
Получена: 11.09.2026 Доработана: 23.10.2026 Принята: 26.10.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 121–122
Аннотация
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.
Ключевые слова: state complexity, language operations, nondeterministic finite automata.
BibTeX
@article{IS-Onishchenko2026,
author = {Онищенко, Сергей},
title = {{}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {121--122},
}
AMSBIB
\RBibitem{IS-Onishchenko2026}
\by С.~Онищенко
\paper
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 121--122
EN