REVIEW
A Circuit Complexity Trichotomy For Regular Languages
Computational Complexity · Submitted 2 Nov 2026 · 21 references
Pith's verdict: A credible and genuinely new trichotomy for regular-language circuit complexity, with a clean lower-bound core; the main caveat is that two load-bearing pieces are inherited from an unpublished self-cited preprint and one logspace reduction is asserted rather than proved.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Every regular language has circuit complexity in exactly one of three tiers — constant, almost-logarithmic, or linear — and the sublinear tier is exactly the new semigroup pseudovariety $X$.
The reading
What carries the argument
The load-bearing object is the new lm-pseudovariety $X$ of semigroup stamps: surjective morphisms $\varphi : \Sigma^+ \to S$ onto finite semigroups, closed under length-multiplying division, in which the identities $(x_0 \cdots x_{m-1})^\omega p_0 \cdots p_{i-1} x_i p_{i+1} \cdots p_{m-1} (y_0 \cdots y_{m-1})^\omega = (x_0 \cdots x_{m-1})^\omega p_0 \cdots p_{i-1} y_i p_{i+1} \cdots p_{m-1} (y_0 \cdots y_{m-1})^\omega$ hold for every $m \geq 1$ and $i < m$ — these identities say that inside an idempotent context, a letter can be exchanged for another letter that sits in the congruent position of an equally long block. Its combinatorial mirror is the diagonal congruence $\simeq_k$, refining the earlier $\approx_k$: two long words are equivalent when their $k$-prefixes and $k$-suffixes agree, their letter frequencies in each residue class modulo $k$ agree up to threshold $k$, and their rare positions agree in label and in all pairwise distances modulo $k$. The bridge from algebra to circuits is the Exchange Principle, which converts a violated $X$-identity into a word pair that the syntactic morphism separates while differing in a single position; the Section 4 gate-counting argument turns one such pair into $\Omega(n)$ required gates. On the constructive side, the machinery is the one-variable Lindström fragment $\mathcal{L}^1$ with bounded quantifiers, whose sentences are evaluated by first locating the positions of a fixed number of rare letters, with two position-extraction circuits (a subpartition threshold construction giving $O(\log^2 n)$ size at constant depth, and an error-correcting-encoder block recursion giving $O(\log n \log\log n)$ size at depth $O((\log\log n)^2)$) supplying the size bounds.
Extended reading notes
Core claim
The central claim, Theorem 1.1, is that the circuit complexity $c(L)$ of every regular language $L \subseteq \Sigma^+$ — the asymptotic minimum number of non-input gates in an unbounded-fan-in AND/OR circuit family over subset-encoded inputs — satisfies exactly one of $c(L) \in O(1)$, $c(L) \in \Omega(\log n) \cap O(\log n \log\log n)$, or $c(L) \in \Omega(n) \cap O(n)$, with $\Omega$ the Hardy–Littlewood 'infinitely often' notion. The classification is driven by Theorem 1.3, a sublinear characterization with ten equivalent faces: $L \in \mathrm{SizeDepth}(O(\log^2 n), O(1))$; $L \in \mathrm{SizeDepth}(O(\log n \log\log n), O((\log\log n)^2))$; $L \in \mathrm{Size}(o(n))$; the syntactic morphism $\eta_L$ belongs to the new lm-pseudovariety $X$; $L$ is a union of $\simeq_k$-classes for some $k$; $L$ is a Boolean combination of finite languages and languages $uKv$ with $K$ a modular disjoint monomial or a modular threshold language; and $L$ is definable in $\mathcal{L}^1[\mathcal{B}[<,+^\omega],\Sigma,<,+^\omega,\bmod,\min,\max]$. The nontrivial lower-bound direction is proved contrapositively in Section 4: a violation of the identities that define $X$ produces words $u, v, w$ and an index $i$ such that the syntactic morphism separates $uv[i \leftarrow u_i]w$ from $uv[i \leftarrow w_i]w$, and from this single witness the authors build, for each input length $n$, a chain of $n-1$ word pairs of length $k(n+1)$ that any correct circuit must separate; since the pairs differ in one position each, any non-input gate can separate at most one pair that its non-input predecessors failed to separate, so $\Omega(n)$ gates are required. The upper bounds run through the logic-to-circuits translation, which reduces everything to computing the binary positions of a constant number of distinguished letters, realized by an $O(\log^2 n)$-size constant-depth circuit (via subpartition threshold schemes) and by an $O(\log n \log\log n)$-size, $O((\log\log n)^2)$-depth circuit (via error-correcting encoders with block recursion).
Load-bearing premise
The classification stands on the $\Omega(n)$ lower bound for languages whose syntactic morphism violates the identities of $X$ — if any such language admitted sublinear circuits, the trichotomy would gain a fourth tier — and the PSPACE-completeness theorems additionally rest on a footnote assertion, without proof, that the cited NFA-universality reduction can be carried out in logarithmic space.
Editorial extensions
If this is right
- The trichotomy closes the question of parallel complexity for regular languages: no regular language can have circuit complexity that is, say, $\Theta(\sqrt{n})$ or $\Theta(\log^2 n)$.
- Sublinear circuit size is a robust, model-independent notion: $o(n)$ size, constant-depth $O(\log^2 n)$ size, and depth-$O((\log\log n)^2)$ size-$O(\log n \log\log n)$ circuits all pick out exactly the same class of regular languages (Theorem 1.3, items 1–3).
- Every regular language of sublinear circuit complexity is definable in $\mathrm{FO}^2[\Sigma,<,\bmod]$ and hence lies in wire-linear $\mathrm{AC}^0$ (Corollaries 1.7–1.8).
- Membership in each of the three tiers is decidable but PSPACE-complete for input NFAs (Theorem 1.4), so the algebraic characterization is effective in principle and intractable in practice.
- For neutral-letter languages the sublinear class simplifies to the classical pseudovariety of aperiodic monoids whose idempotents commute with every element, equivalently Boolean combinations of disjoint monomials (Theorem 1.5).
Reading between the lines
- Editorial extension: the paper's Proposition 3.15 shows the two nontrivial tiers cannot be told apart by the stable semigroup — $(a+b)^*c(a+b)c(a+b)^*$ and $(a+b)^*cac(a+b)^*$ have isomorphic stable semigroups but land on opposite sides of the divide — so any algebraic characterization of sublinear complexity must use the length-multiplying structure of stamps. A testable consequence is that no fi
- Editorial extension: all the upper bounds factor through one promise problem, $\mathrm{Occ}_t$ (output the binary positions of the exactly $t$ marked positions of an $n$-bit word). If that combinatorial problem had $O(\log n)$-size constant-depth circuits for every fixed $t$, then every sublinear regular language would sit in $\mathrm{SizeDepth}(O(\log n), O(1))$ and the middle tier would collapse
- Editorial extension: the two characterizations in the sublinear theorem are modular through and through — residue classes modulo $k$, thresholds, and modular predicates — which makes it plausible that the same trichotomy, with $X$ adjusted, survives when the circuit basis is extended with $\mathrm{MOD}_m$ gates or majority gates; the paper lists this as an open direction, and a concrete first test
Original abstract
We establish a trichotomy for the non-uniform, unbounded-fan-in circuit complexity of regular languages: the complexity of every regular language lies in exactly one of $O(1)$, $\Omega(\log n)\cap O(\log n\log\log n)$, or $\Omega(n)\cap O(n)$. Our main technical contribution is a characterization of the sublinear class in terms of algebra, word congruences, regular expressions, and logic. This class consists precisely of the regular languages computable by constant-depth circuits of size $O(\log^2 n)$, or, equivalently, by circuits of size $O(\log n\log\log n)$ and depth $O((\log\log n)^2)$. Consequently, every regular language of sublinear circuit complexity is definable in $\mathrm{FO}^2[\Sigma,<,\mathrm{mod}]$, which is contained in wire-linear $\mathbf{AC}^0$. For each of the three classes, deciding membership is $\mathbf{PSPACE}$-complete when the language is specified by a nondeterministic finite automaton. We also obtain a corresponding classification for regular languages with a neutral letter.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We establish a trichotomy for the non-uniform, unbounded-fan-in circuit complexity of regular languages: the complexity of every regular language lies in exactly one of $O(1)$, $\Omega(\log n)\cap O(\log n\log\log n)$, or $\Omega(n)\cap O(n)$. Our main technical contribution is a characterization of the sublinear class in terms of algebra, word congruences, regular expressions, and logic. This class consists precisely of the regular languages computable by constant-depth circuits of size $O(\log^2 n)$, or, equivalently, by circuits of size $O(\log n\log\log n)$ and depth $O((\log\log n)^2)$. Consequently, every regular language of sublinear circuit complexity is definable in $\mathrm{FO}^2[\Sigma,<,\mathrm{mod}]$, which is contained in wire-linear $\mathbf{AC}^0$. For each of the three classes, deciding membership is $\mathbf{PSPACE}$-complete when the language is specified by a nondeterministic finite automaton. We also obtain a corresponding classification for regular languages with a neutral letter.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We establish a trichotomy for the non-uniform, unbounded-fan-in circuit complexity of regular languages: the complexity of every regular language lies in exactly one of $O(1)$, $\Omega(\log n)\cap O(\log n\log\log n)$, or $\Omega(n)\cap O(n)$. | result 0.86 | 0.94 | 0.93 | asserted 1.00 |
| s1 | Our main technical contribution is a characterization of the sublinear class in terms of algebra, word congruences, regular expressions, and logic. | contribution 1.00 | 0.94 | 0.11 | asserted 1.00 |
| s2 | This class consists precisely of the regular languages computable by constant-depth circuits of size $O(\log^2 n)$, or, equivalently, by circuits of size $O(\log n\log\log n)$ and depth $O((\log\log n)^2)$. | result 0.92 | 0.84 | 0.10 | asserted 1.00 |
| s3 | Consequently, every regular language of sublinear circuit complexity is definable in $\mathrm{FO}^2[\Sigma,<,\mathrm{mod}]$, which is contained in wire-linear $\mathbf{AC}^0$. | result 0.52 | 0.81 | 0.09 | asserted 1.00 |
| s4 | For each of the three classes, deciding membership is $\mathbf{PSPACE}$-complete when the language is specified by a nondeterministic finite automaton. | result 0.98 | 0.82 | 0.07 | asserted 1.00 |
| s5 | We also obtain a corresponding classification for regular languages with a neutral letter. | result 0.74 | 0.91 | 0.03 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2611.03615 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.