Answers are grounded in this paper and cite their sources.
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)$, Ω(log n)∩ O(log nloglog n), or Ω(n)∩ 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² n), or, equivalently, by circuits of size O(log nloglog n) and depth O((loglog n)²). Consequently, every regular language of sublinear circuit complexity is definable in FO²[Σ,<,mod], which is contained in wire-linear AC⁰. For each of the three classes, deciding membership is 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.
No takes yet. Share an insight, caveat, or question.
Göller et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: