FO-uniform AC0 z pewnym orzeczeniem

Moje pytanie dotyczy teorii modeli skończonych / złożoności opisowej, więc $FO(R)$ będzie oznaczać „pierwszy rząd nad skończonymi słowami binarnymi, przy użyciu predykatów Rs i jednoargumentowego predykatu P true na pozycji 1 w słowie”.

Chciałbym wiedzieć, czy jest jakakolwiek caracterization $FO(<,R)$ z R dowolnym orzeczeniem $\mathbb N^r$dla jakiegoś r? Na przykład na$FO(<,+)$lub $FO(<,P_2)$ gdzie $P_2$ jest zbiorem potęgi 2. Szczególnie wydaje mi się, że powinna być równa $AC^0$ z pewnymi warunkami jednolitości, ale nie mogę znaleźć żadnego wyniku, który by to stwierdził.

Oto, co już wiem, dla pewnej wartości $R$.

Jak powszechnie wiadomo $FO(<,bit)$, logika pierwszego rzędu dla słów z porządkiem i predykatem bitowym jest równa $AC^0$-$FO(<,bit)$mundur. Oznacza to, że oboje rozpoznają dokładnie te same języki. Patrz na przykład „Opisowa złożoność” Immermana, strona 82. (Jest również równy wielu innym cechom karakteryzacyjnym, takim jak$AC^0$-logowa jednolita i stała maszyna o swobodnym dostępie równoległym, ale nie tego tu szukam.)

Jeśli możemy użyć dowolnego predykatu numerycznego w logice pierwszego rzędu, to mamy $AC^0$ (niejednolity), jeśli $C$ jest klasą funkcji zawierającą funkcję obliczalną w czasie dziennika $FO(<,C)$ jest równe $AC^0-C$-uniform (dla tych dwóch wyników patrz Barrington, „ Extensions of a Idea of ​​Mc-Naughton ”, 1993).

Wreszcie $FO(<)$ jest klasą języka bez gwiazd (język, który można zdefiniować wyrażeniem regularnym bez użycia gwiazdy Kleene), ale nie daje żadnych informacji pod względem złożoności obwodu.

Nie jestem do końca pewien, czego szukasz, ale następujące mogą być dla Ciebie interesujące:

1. Idea, że ​​ograniczenie liczbowych predykatów we wzorze FO odpowiada warunkom jednorodności, jest wyraźnie zbadana, na przykład w pracy „FO (<) - jednorodność” autorstwa Behle i Lange.
2. Badanie „Arytmetyka, logika pierwszego rzędu i kwantyfikatory zliczania” Schweikardta zawiera między innymi przegląd znanych wyników dotyczących mocy ekspresyjnej różnych predykatów arytmetycznych