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

<ol>
<li>The idea that restricting numerical predicates in FO-formula corresponds to uniformity conditions is explicitly investigated, for example, in the paper
<a href="http://fuseki.informatik.uni-tuebingen.de/~lange/Arbeiten/BeLa/uniform.ps.gz">"FO(&lt;)-uniformity"</a> by Behle and Lange.</li>
<li>The survey <a href="http://www.tks.informatik.uni-frankfurt.de/getpdf?id=466">"Arithmetic, first-order logic, and counting quantifiers"</a>
by Schweikardt provides i.a. an overview of known results about
the expressive power of different arithmetical predicates</li>
</ol>

CC BY-SA 3.0
2012-07-24T08:51:18.990Z
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
CC BY-SA 3.0
2012-07-23T18:43:50.963Z
2012-07-23T18:43:50.963Z
f-h
<p>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".</p>

<p>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.</p>

<p>Here is what I already know, for some value of $R$.</p>

<p>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.)</p>

<p>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, "<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.9364">Extensions of an Idea of Mc-Naughton</a>", 1993).</p>

<p>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.</p>

<cc.complexity-theory><lo.logic><circuit-complexity><descriptive-complexity><finite-model-theory>
FO-uniform AC0 with some predicate
Arthur MILCHIOR
# FO-uniform AC0 with some predicate

(Asked by: username_0 on 2012-07-22)

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.9364)", 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.

**Tags:** cc.complexity-theory, lo.logic, circuit-complexity, descriptive-complexity, finite-model-theory


---

## 1 answers

### Answer by username_1 on 2012-07-23. Score: 7 | Accepted 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"](http://fuseki.informatik.uni-tuebingen.de/~lange/Arbeiten/BeLa/uniform.ps.gz) by Behle and Lange.
2. The survey ["Arithmetic, first-order logic, and counting quantifiers"](http://www.tks.informatik.uni-frankfurt.de/getpdf?id=466)
   by Schweikardt provides i.a. an overview of known results about
   the expressive power of different arithmetical predicates

> **Comments:**
> **username_0**: 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.  

---

