Relation between $AC^0$ and regular languages

Question

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

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, Feb 07 '13 at 15:48
The Zoo uses the notation REG: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#reg — András Salamon, Feb 07 '13 at 16:59

dd1 · Accepted Answer · 2013-02-08T08:44:50.450

25

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

edited Feb 08 '13 at 08:44

answered Feb 07 '13 at 15:54

dd1

537
5
10

11

It would be helpful if you could summarize the answer here as well. – Suresh Venkat Feb 07 '13 at 17:34
3

Done, although I do not really understand the point of doing so in this particular case. – dd1 Feb 08 '13 at 08:45
7

It's mainly to keep the answer self-contained as much as possible. – Suresh Venkat Feb 08 '13 at 08:46
2

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 01:36

score 10 · Answer 2 · answered Oct 03 '13 at 11:25

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.

Relation between $AC^0$ and regular languages

2 Answers2