Restricted Minimal Linear Languages: A Formal Characterization of $\text{AC}^{0}$
G. L. Praveen, K. Sunil · 2025
We introduce Restricted Minimal Linear Languages (RmLIN), a syntactically constrained subclass of context-free languages defined by fixed-context, recursive rules with a single non-terminal. Despite their simplicity, RmLIN grammars generate non-regular languages such as$\left\{a^{n} b^{n}\right\}$, while provably excluding counting-based languages like Parity and Majority. We define an automaton model, the Restricted Context-Matching Two-Head Automaton (RCM-2HA), that characterizes RmLIN. Crucially, we prove that the class of languages generated by RmLIN grammars is exactly the class$\mathbf{A C}^{0}$- constant-depth, polynomial-size Boolean circuits. This syntactic characterization of a semantic complexity class bridges formal language theory with circuit complexity and opens new avenues for low-level computation analysis.