# 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(<,R)$ with R any predicate on $\mathbb N^r$ for some r? For example on $FO(<,+)$, or $FO(<,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(<,bit)$, the first order logic on words with an order and a bit predicate is equal to $AC^0$-$FO(<,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(<,C)$ is equal to $AC^0-C$-uniform (for these two results see Barrington, "Extensions of an Idea of Mc-Naughton", 1993).

Finally $FO(<)$ 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.

## 1 Answer

I am not completely sure what you are looking for, but the following might be interesting to you:

1. The idea that restricting numerical predicates in FO-formula corresponds to uniformity conditions is explicitly investigated, for example, in the paper "FO(<)-uniformity" by Behle and Lange.
2. 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
• Thank you a lot, the first of those two papers was exactly what I was searching for. I did prove a part of its result, and I was pretty sure that someone would have arlready proved it as the proof is almost the same than the proof about FO(<,bit) uniformity. – Arthur MILCHIOR Jul 24 '12 at 8:51