FO0 uniforme AC0 con algún predicado

Mi pregunta es acerca de la teoría del modelo finito / complejidad descriptiva, por lo que significará "primer orden sobre palabras binarias finitas, usando predicados Rs y un predicado unario P verdadero en la posición del 1 en la palabra".$FO(R)$

Me gustaría saber, ¿hay alguna caracterización de con R algún predicado en N r para algún r? Por ejemplo, en F O ( < , + ) o F O ( < , P 2 ) donde P 2 es el conjunto de potencia de 2. Especialmente, me parece que debería ser igual a A C 0 con alguna condición de uniformidad , pero no puedo encontrar ningún resultado que indique esto.$FO(<,R)$$\mathbb N^r$$FO(<,+)$$FO(<,P_2)$$P_2$$AC^0$

Esto es lo que ya sé, para algún valor de .$R$

Es bien sabido que , la lógica de primer orden en palabras con un orden y un predicado de bit es igual a A C 0 - F O ( < , b i t ) uniforme. Con esto significa que ambos reconocen exactamente los mismos idiomas. Consulte, por ejemplo, "Complejidad descriptiva" de Immerman, página 82. (También es igual a muchas otras caracterizaciones, como el uniforme de tiempo de registro A C 0 y la máquina de acceso aleatorio paralelo de tiempo constante, pero no es lo que soy buscando aquí.)$FO(<,bit)$$AC^0$$FO(<,bit)$$AC^0$

Si podemos usar un predicado numérico arbitrario en nuestra lógica de primer orden, entonces tenemos (no uniforme), si C es una clase de función que contiene la función computable de tiempo de registro, entonces F O ( < , C ) es igual a A C 0 - C -uniforme (para estos dos resultados ver Barrington, " Extensiones de una idea de Mc-Naughton ", 1993).$AC^0$$C$$FO(<,C)$$AC^0-C$

Finalmente, es la clase de lenguaje libre de estrellas (lenguaje que puede definirse mediante una expresión regular que no usa la estrella de Kleene), pero esto no proporciona información en términos de complejidad del circuito.$FO(<)$

No estoy completamente seguro de lo que está buscando, pero lo siguiente puede ser interesante para usted:

1. Behle y Lange investigan explícitamente la idea de que restringir los predicados numéricos en la fórmula FO corresponde a condiciones de uniformidad, por ejemplo, en el artículo "FO (<) - uniformidad" .
2. La encuesta "Aritmética, lógica de primer orden y cuantificadores de conteo" de Schweikardt proporciona, entre otras cosas, una visión general de los resultados conocidos sobre el poder expresivo de los diferentes predicados aritméticos.