arxiv: 2605.02957 · v1 · submitted 2026-05-02 · 💻 cs.FL

Recognition: unknown

Nondeterministic state complexity of square root

Sergey Onishchenko

Authors on Pith no claims yet

Pith reviewed 2026-05-10 14:44 UTC · model grok-4.3

classification 💻 cs.FL

keywords state complexitynondeterministic finite automatasquare root operationregular languageslanguage operationsnondeterminism

0 comments

The pith

The square root of a language accepted by an n-state NFA requires an NFA with up to n^3 states in the worst case.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper studies the nondeterministic state complexity of the square-root operation on regular languages, where sqrt(L) consists of all words w such that the concatenation ww belongs to L. It was already known that any n-state NFA for L can be converted to an NFA for sqrt(L) using at most n^3 states. The contribution is a matching lower bound: there exist languages accepted by n-state NFAs for which every NFA accepting sqrt(L) needs at least n^3 states. This completely determines the worst-case state complexity as Theta(n^3). Understanding this helps in analyzing how language operations scale the size of automata representations.

Core claim

For regular languages accepted by n-state nondeterministic finite automata, the square-root operation can always be realized by an NFA with n^3 states, and this number is tight because there are languages where n^3 states are required.

What carries the argument

A specific family of witness languages accepted by n-state NFAs whose square roots force any accepting NFA to have at least n^3 states, combined with the general cubic upper-bound construction.

If this is right

The square-root operation on regular languages has nondeterministic state complexity exactly n^3 in the worst case.
Any language accepted by an n-state NFA has its square root accepted by some NFA with at most n^3 states.
There exist languages accepted by n-state NFAs requiring at least n^3 states for their square roots.
The previous gap between the n^3 upper bound and the roughly n^3 lower bound is now closed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This result suggests that similar cubic bounds might hold for other language operations involving concatenation or repetition.
The construction techniques may apply to proving tight bounds for state complexity of other derived languages.
Researchers could investigate the deterministic state complexity of the same operation to compare it with the nondeterministic case.

Load-bearing premise

There is a family of languages, each accepted by an n-state NFA, such that no smaller than n^3 state NFA can accept their square roots.

What would settle it

Constructing an n-state NFA accepting a language L for which sqrt(L) is accepted by an NFA with o(n^3) states as n grows large.

read the original 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). In this paper, we close this gap completely and prove that $n^{3}$ states are sufficient and necessary in the worst case.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper closes the gap by showing the NFA state complexity of sqrt(L) is exactly n^3.

read the letter

The key result here is that the nondeterministic state complexity of the square root operation on regular languages is exactly n^3 in the worst case. For an n-state NFA accepting L, sqrt(L) can always be accepted by an NFA with at most n^3 states, and the paper gives an explicit family of languages where that many states are required. This improves the prior lower bound of (n-1)(n-2)(n-3) and makes the bound tight. The upper bound construction was already known, so the main work is the matching lower bound argument and the concrete automata that witness it. The constructions appear carefully chosen to create the necessary distinctions in the square root language, forcing the state count up to n^3. The manuscript lays out both directions with enough detail to follow the steps without gaps in the logic. The presentation is straightforward, with the automata described directly and the necessity argument built step by step. No circularity or unfalsifiable claims show up in the argument. The soft spots are minor and expected for this kind of work. The result stays tightly focused on one operation, which keeps its reach within automata theory rather than suggesting broader techniques. There is little discussion of how this interacts with other operations like concatenation or other roots, but that is not a flaw in the current claim. The citations cover the relevant prior state complexity results without overclaiming. This paper is for researchers who track exact state complexity bounds for regular language operations. Someone working in that corner of automata theory will find the tight bound useful for reference or further comparisons. It deserves a serious referee because the central claim is now fully supported by explicit constructions on both sides. I would send it to peer review; the evidence is in place and the improvement is clear.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that the nondeterministic state complexity of the square-root operation √L = {w | ww ∈ L} is exactly n³ in the worst case. It establishes an upper bound of n³ states for an NFA accepting √L when L is accepted by an n-state NFA, and supplies an explicit family of n-state NFAs for which any NFA accepting √L requires n³ states, improving the prior lower bound of (n-1)(n-2)(n-3).

Significance. If the proofs hold, the result closes the gap in the literature on NFA state complexity of regular-language operations by establishing a tight Θ(n³) bound. The explicit construction witnessing the matching lower bound is a concrete strength, as is the direct (non-asymptotic) nature of the argument.

minor comments (2)

[§4] §4, construction of the lower-bound family: the transition function on the 'witness' states is described only by cases; an explicit table or diagram for small n would improve verifiability.
[§3] The proof of the upper bound (already known) is sketched rather than fully re-derived; a one-paragraph recap of the n³ construction would make the manuscript self-contained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive evaluation of our manuscript. The referee's summary correctly identifies the main result: a tight n³ bound on the nondeterministic state complexity of the square-root operation. No major comments were raised in the report, so we have no specific points to address. We will make any minor editorial changes requested by the editor during the revision.

Circularity Check

0 steps flagged

No significant circularity; bounds proved by explicit construction

full rationale

The paper establishes an upper bound of n^3 states for an NFA accepting sqrt(L) (previously known) and a matching lower bound via an explicit family of n-state NFAs. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear; the lower-bound witness is constructed directly from the definition of sqrt(L) without reducing to prior results by the same authors. The derivation chain is self-contained against external automata constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard automata constructions for the upper bound and an explicit family of languages for the lower bound; no free parameters or invented entities are introduced.

axioms (1)

standard math Standard properties of NFAs and regular language operations
The square-root operation and NFA constructions are defined within classical automata theory.

pith-pipeline@v0.9.0 · 5381 in / 1066 out tokens · 35097 ms · 2026-05-10T14:44:34.865357+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references

[1]

Holzer and Kutrib, Nondeterministic Descriptional Complexity of Regular Languages,International Journal of Foundations of Computer Science, 14(6):1087–1102, 2003

2003
[2]

Okhotin and Salomaa, Further Closure Properties of Input-Driven Pushdown Automata,Theoretical Computer Science, 798:65–77, 2019

2019
[3]

Caron, Hamel-De Le Court, Luque, and Patrou, New Tools for State Complexity,Discrete Mathematics & Theoret- ical Computer Science, 22(1), article 9, 2020

2020
[4]

Maslov, Estimates of the Number of States of Finite Automata,Soviet Mathematics Doklady, 11(5):1373–1375, 1970

1970
[5]

Birget, J.-C., Intersection and union of regular languages and state complexity,Information Processing Letters, 43(4), 185–190, 1992

1992
[6]

S. Yu, Q. Zhuang, and K. Salomaa, The state complexities of some basic operations on regular languages,Theoret- ical Computer Science, 125(2):315–328, 1994

1994
[7]

Salomaa, D

A. Salomaa, D. Wood, and S. Yu, On the state complexity of reversals of regular languages,Theoretical Computer Science, 320(2–3):315–329, 2004

2004
[8]

Domaratzki and A

M. Domaratzki and A. Okhotin, State complexity of power,Theoretical Computer Science, 410(24–25):2377–2392, 2009

2009
[9]

Jirásková and A

G. Jirásková and A. Okhotin, State complexity of cyclic shift,RAIRO – Theoretical Informatics and Applications, 42(2):335–360, 2008

2008
[10]

Y.-S. Han, K. Salomaa, and D. Wood, Nondeterministic state complexity of basic operations for prefix-free regular languages,Fundamenta Informaticae, 90(1–2):93–106, 2009

2009
[11]

Goˇ c, A

D. Goˇ c, A. Palioudakis, and K. Salomaa, Nondeterministic state complexity of proportional removals,Interna- tional Journal of Foundations of Computer Science, 25(7):823–835, 2014

2014
[12]

Hospodár, J

M. Hospodár, J. Jirásek, G. Jirásková, and J. Šebej, Operational complexity: NFA-to-DFA trade-off,Information and Computation, 307:105369, 2025

2025
[13]

B. Cui, Y. Gao, L. Kari, and S. Yu, State complexity of combined operations with two basic operations,Theoretical Computer Science, 437:82–102, 2012. 5

2012