Relação entre e idiomas regulares

Seja a classe de todos os idiomas regulares.$\mathsf{REG}$

É conhecido e \ mathsf {REG} \ não \ subconjunto \ mathsf {AC} ^ 0 . Mas existe alguma caracterização para idiomas em \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?$\mathsf{AC}^0 \not\subset \mathsf{REG}$$\mathsf{REG} \not\subset \mathsf{AC}^0$$\mathsf{AC}^0 \cap \mathsf{REG}$

O artigo a seguir parece conter uma resposta:

Misture Barrington, DA, Compton, K., Straubing, H., Therien, D.: Línguas regulares em $\mathsf{NC}^1$ . Jornal de Ciências da Computação e Sistemas 44 (3), 478-499 (1992) ( link )

Uma das caracterizações obtidas é a seguinte. A classe $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ contém exatamente os idiomas que podem ser obtidos em $\{0\}$ , $\{1\}$ e $\mathsf{LENGTH}(q)$ para $q > 1$ com um número finito de operações e concatenações booleanas. Aqui todo idioma $\mathsf{LENGTH}(q)$ contém todas as strings cujo comprimento é divisível por $q$ . (Há também uma caracterização lógica e duas algébricas.)

Os idiomas regulares dentro do são um subconjunto "legal" dos idiomas regulares. Eles têm boas caracterizações lógicas e algébricas.$AC^0$

O livro "Autômatos finitos, lógica formal e complexidade de circuitos" de Straubing considera essas questões.

Sua pergunta pode ser respondida da seguinte maneira.

$AC^0 \cap REG$ = = idiomas reconhecidos por monoides quase aperiódicos.$FO[<,Suc,\equiv]$

Aqui é uma lógica de primeira ordem, usando predicados numéricos menos que, sucessor e .$FO[<,Suc,\equiv]$$x \equiv (0 ~mod ~q)$

Outra caracterização mostrada em "Idiomas regulares em " é o conjunto de idiomas que pode ser formado usando um conjunto finito de alfabetos, LENGTH (q) e fechá-lo sob combinações e concatenações booleanas.$NC^1$