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.


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
  • $\begingroup$ 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. $\endgroup$ – Arthur MILCHIOR Jul 24 '12 at 8:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.