FO-Uniform AC0 mit einem Prädikat

Meine Frage bezieht sich auf die endliche Modelltheorie / deskriptive Komplexität, daher bedeutet "erste Ordnung über endlichen binären Wörtern unter Verwendung der Prädikate Rs und eines unären Prädikats P, das an der Position der 1 im Wort wahr ist".$FO(R)$

Ich würde gerne wissen, gibt es eine Charakterisierung von mit R ein Prädikat für N r für einige r? Zum Beispiel auf F O ( < , + ) oder F O ( < , P 2 ), wobei P 2 die Potenzmenge von 2 ist. Insbesondere scheint es mir, dass es mit einer gewissen Gleichförmigkeitsbedingung gleich A C 0 sein sollte , aber ich kann kein Ergebnis finden, das dies besagt.$FO(<,R)$$\mathbb N^r$$FO(<,+)$$FO(<,P_2)$$P_2$$AC^0$

Hier ist , was ich schon weiß, für einen Wert von .$R$

Es ist bekannt, dass , die Logik erster Ordnung für Wörter mit einer Ordnung und einem Bitprädikat, gleich A C 0 - F O ( < , b i t ) einheitlich ist. Dies bedeutet, dass beide genau die gleichen Sprachen erkennen. Siehe zum Beispiel "Beschreibende Komplexität" von Immerman, Seite 82. (Es entspricht auch vielen anderen Charakterisierungen, wie z. B. A C 0 -Logzeituniform und zeitlich konstanter Parallelzugriffsmaschine, aber es ist nicht das, was ich bin hier suchen.)$FO(<,bit)$$AC^0$$FO(<,bit)$$AC^0$

Wenn wir in unserer Logik erster Ordnung ein beliebiges numerisches Prädikat verwenden können, haben wir (ungleichmäßig). Wenn C eine Funktionsklasse ist, die die logarithmisch berechenbare Funktion enthält, ist F O ( < , C ) gleich A C 0 - C -uniform (für diese beiden Ergebnisse siehe Barrington, " Extensions of a Idea of ​​Mc-Naughton ", 1993).$AC^0$$C$$FO(<,C)$$AC^0-C$

Schließlich ist die Klasse der sternfreien Sprache (Sprache, die durch einen regulären Ausdruck ohne Kleene-Stern definiert werden kann), die jedoch keine Informationen hinsichtlich der Schaltungskomplexität liefert.$FO(<)$

Ich bin mir nicht ganz sicher, wonach Sie suchen, aber Folgendes könnte für Sie interessant sein:

1. Die Idee, dass die Einschränkung numerischer Prädikate in der FO-Formel Gleichförmigkeitsbedingungen entspricht, wird beispielsweise in der Arbeit "FO (<) - Gleichförmigkeit" von Behle und Lange explizit untersucht .
2. Die Umfrage "Arithmetik, Logik erster Ordnung und Zählquantifizierer" von Schweikardt bietet unter anderem einen Überblick über bekannte Ergebnisse zur Ausdruckskraft verschiedener arithmetischer Prädikate