Relación entre y lenguajes regulares

Deje que sea ​​la clase de todos los idiomas regulares.$\mathsf{REG}$

Se conoce y \ mathsf {REG} \ not \ subset \ mathsf {AC} ^ 0 . Pero, ¿hay alguna caracterización de idiomas en \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?$\mathsf{AC}^0 \not\subset \mathsf{REG}$A C 0 ∩ R E $\mathsf{REG} \not\subset \mathsf{AC}^0$$\mathsf{AC}^0 \cap \mathsf{REG}$

El siguiente documento parece contener una respuesta:

Mix Barrington, DA, Compton, K., Straubing, H., Therien, D .: Idiomas regulares en $\mathsf{NC}^1$ . Journal of Computer and System Sciences 44 (3), 478-499 (1992) ( enlace )

Una de las caracterizaciones obtenidas allí es la siguiente. La clase $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ contiene exactamente esos idiomas que se pueden obtener de $\{0\}$ , $\{1\}$ y $\mathsf{LENGTH}(q)$ para $q > 1$ con un número finito de operaciones booleanas y concatenaciones. Aquí cada idioma $\mathsf{LENGTH}(q)$ contiene todas las cadenas cuya longitud es divisible por $q$ . (También hay una caracterización lógica y dos algebraicas).

Los idiomas regulares dentro de son un subconjunto "agradable" de los idiomas regulares. Tienen buenas caracterizaciones lógicas y algebraicas.$AC^0$

El libro "Autómatas finitos, lógica formal y complejidad del circuito" de Straubing considera estas preguntas.

Su pregunta puede ser respondida de la siguiente manera.

F O [ < , S u c , ≡ $AC^0 \cap REG$ = = idiomas reconocidos por los monoides cuasi-aperiódicos.$FO[<,Suc,\equiv]$

Aquí es lógica de primer orden utilizando predicados numéricos menores que, sucesores y .x ≡ ( 0 m o d q $FO[<,Suc,\equiv]$$x \equiv (0 ~mod ~q)$

Otra caracterización como se muestra en "Idiomas regulares en " es el conjunto de idiomas que se pueden formar usando un conjunto finito de alfabetos, LONGITUD (q) y cerrándolo bajo combinaciones booleanas y concatenaciones.$NC^1$