20
$\begingroup$

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

$\endgroup$
24
$\begingroup$

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

$\endgroup$
  • 10
    $\begingroup$ It would be helpful if you could summarize the answer here as well. $\endgroup$ – Suresh Venkat Feb 7 '13 at 17:34
  • 3
    $\begingroup$ Done, although I do not really understand the point of doing so in this particular case. $\endgroup$ – dd1 Feb 8 '13 at 8:45
  • 7
    $\begingroup$ It's mainly to keep the answer self-contained as much as possible. $\endgroup$ – Suresh Venkat Feb 8 '13 at 8:46
  • 1
    $\begingroup$ 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$. $\endgroup$ – J.-E. Pin Aug 28 '13 at 1:36
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.