# Relation between $AC^0$ and regular languages

Let $\mathsf{REG}$ be the class of all regular languages.

It is known $\mathsf{AC}^0 \not\subset \mathsf{REG}$ and $\mathsf{REG} \not\subset \mathsf{AC}^0$. But is there any characterization for languages in $\mathsf{AC}^0 \cap \mathsf{REG}$?

The following paper seems to contain an answer:

Mix Barrington, D. A., Compton, K., Straubing, H., Therien, D.: Regular languages in $\mathsf{NC}^1$. Journal of Computer and System Sciences 44(3), 478-499 (1992) (link)

One of the characterizations obtained there is as follows. The class $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ contains exactly those languages that can be obtained from $\{0\}$, $\{1\}$ and $\mathsf{LENGTH}(q)$ for $q > 1$ with a finite number of Boolean operations and concatenations. Here every language $\mathsf{LENGTH}(q)$ contains all strings whose length is divisible by $q$. (There is also a logical characterization and two algebraic ones.)

• It would be helpful if you could summarize the answer here as well. – Suresh Venkat Feb 7 '13 at 17:34
• Done, although I do not really understand the point of doing so in this particular case. – dd1 Feb 8 '13 at 8:45
• It's mainly to keep the answer self-contained as much as possible. – Suresh Venkat Feb 8 '13 at 8:46
• Note that the algebraic characterization yields an algorithm to decide whether a given regular language belongs or not to $\mathsf{REG} \cap \mathsf{AC}^0$. – J.-E. Pin Aug 28 '13 at 1:36

The regular languages inside $AC^0$ are a "nice" subset of the regular languages. They have nice logical as well as algebraic characterizations.

The book "Finite Automata, Formal Logic and Circuit Complexity" by Straubing considers these questions.

$AC^0 \cap REG$ = $FO[<,Suc,\equiv]$ = languages recognized by quasi-aperiodic monoids.
Here $FO[<,Suc,\equiv]$ is first order logic using less than, successor and $x \equiv (0 ~mod ~q)$ numerical predicates.
Another characterization as shown in "Regular languages in $NC^1$" are the set of languages which can be formed using a finite set of alphabets, LENGTH(q) and closing it under boolean combinations and concatenations.