Regular languages fall into three circuit complexity categories
A Circuit Complexity Trichotomy For Regular Languages
Computational ComplexityFormal Languages and Automata Theory
Summary
The authors studied how complicated it is to build circuits that recognize regular languages, which are simple patterns processed by computers. They found every regular language fits into one of three clear groups based on how big or complex the circuit needs to be. They also figured out how to tell which group a language belongs to, even if it’s described by a machine called a nondeterministic finite automaton. This helps us understand the fundamental limits of computing simple patterns efficiently.
What this means in practice
- •For circuit designers: Determine the minimal circuit depth and size needed for hardware recognizing regular languages during design.
- •For compiler developers: Optimize pattern matching components by classifying regular languages into circuit complexity classes to improve efficiency.
A theory result. No direct application yet.
Authors
Stefan Göller, Amaldev Manuel
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)$, $Ω(\log n)\cap O(\log n\log\log n)$, or $Ω(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[Σ,<,\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.