FO-uniform AC0 with some predicate My question is about finite model theory/descriptive complexity, so $FO(R)$ will mean "first order over finite binary words, using predicates Rs and a unary predicate P true on the position of the 1 in the word".

I would like to know, are there any caracterisation of $FO(&lt;,R)$ with R any predicate on $\mathbb N^r$ for some r? For example on $FO(&lt;,+)$, or $FO(&lt;,P_2)$ where $P_2$ is the set of power of 2. Especially, it seems to me that it should be equal to $AC^0$ with some uniformity condition, but I can not find any resultat that states this.

Here is what I already know, for some value of $R$.

It is well known that $FO(&lt;,bit)$, the first order logic on words with an order and a bit predicate is equal to $AC^0$-$FO(&lt;,bit)$ uniform. By this it means they both recognise exactly the same languages.  See for example "Descriptive complexity" of Immerman, page 82.
(It is also equal to a lot of other caracterisation, such as $AC^0$-logtime uniform, and constant-time parallel random access machine, but it is not what I am searching for here.)

If we can use arbitrary numerical predicate in our first order logic, then we have $AC^0$ (non uniform), if $C$ is a class of function containing the log-time computable function, then $FO(&lt;,C)$ is equal to $AC^0-C$-uniform (for these two results see Barrington, "Extensions of an Idea of Mc-Naughton", 1993).

Finally $FO(&lt;)$ is the class of star-free language (language that can be defined by a regular expression using no Kleene star), but this give no information in term of circuit complexity.
I am not completely sure what you are looking for, but the following might 
be interesting to you:


The idea that restricting numerical predicates in FO-formula corresponds to uniformity conditions is explicitly investigated, for example, in the paper
"FO(&lt;)-uniformity" by Behle and Lange.
The survey "Arithmetic, first-order logic, and counting quantifiers"
by Schweikardt provides i.a. an overview of known results about
the expressive power of different arithmetical predicates