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

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

<p>Your question can be answered as follows.</p>

<p>$AC^0 \cap REG$ = $FO[&lt;,Suc,\equiv]$ = languages recognized by quasi-aperiodic monoids.</p>

<p>Here $FO[&lt;,Suc,\equiv]$ is first order logic using less than, successor and $x \equiv (0 ~mod ~q)$ numerical predicates.</p>

<p>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.</p>

CC BY-SA 3.0
2013-10-03T11:25:20.503Z
2013-10-03T11:25:20.503Z
Sreejith A V
<p>The following paper seems to contain an answer:</p>

<p>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) (<a href="http://deepblue.lib.umich.edu/bitstream/2027.42/30017/1/0000385.pdf">link</a>)</p>

<p>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 &gt; 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.)</p>

CC BY-SA 3.0
2013-02-07T17:34:47.077Z
It would be helpful if you could summarize the answer here as well.
Suresh Venkat
CC BY-SA 3.0
2013-02-08T08:45:58.700Z
Done, although I do not really understand the point of doing so in this particular case.
dd1
CC BY-SA 3.0
2013-02-08T08:46:43.283Z
It's mainly to keep the answer self-contained as much as possible.
Suresh Venkat
CC BY-SA 3.0
2013-08-28T01:36:42.153Z
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
CC BY-SA 3.0
2013-02-07T15:54:15.157Z
2013-02-08T08:44:50.450Z
2013-02-08T08:44:50.450Z
dd1
<p>Let <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aR#reg">$\mathsf{REG}$</a> be the class of all regular languages. </p>

<p>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}$?</p>

CC BY-SA 3.0
2013-02-07T15:48:55.517Z
[RL](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#rl) often denotes the class of problems solvable in randomized logarithmic space.  Can you switch to some other notation and/or define it in the body of the question?
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-07T16:59:03.293Z
The Zoo uses the notation REG: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#reg
András Salamon
<circuit-complexity><regular-language>
Relation between $AC^0$ and regular languages
Alex Grilo
# Relation between $AC^0$ and regular languages

(Asked by: username_0 on 2013-02-07)

Let [$\mathsf{REG}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aR#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}$?

**Tags:** circuit-complexity, regular-language

> **Comments:**
> **username_1**: [RL](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#rl) often denotes the class of problems solvable in randomized logarithmic space.  Can you switch to some other notation and/or define it in the body of the question?  
> **username_2**: The Zoo uses the notation REG: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#reg  

---

## 2 answers

### Answer by username_4 on 2013-02-07. Score: 25 | Accepted answer

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](http://deepblue.lib.umich.edu/bitstream/2027.42/30017/1/0000385.pdf))

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.)

> **Comments:**
> **username_5**: It would be helpful if you could summarize the answer here as well.  
> **username_4**: Done, although I do not really understand the point of doing so in this particular case.  
> **username_5**: It's mainly to keep the answer self-contained as much as possible.  
> **username_6**: 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$.  

---

### Answer by username_3 on 2013-10-03. Score: 10

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.

Your question can be answered as follows.

$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.


---

