AC0 uniforme de FO com algum predicado

Minha pergunta é sobre teoria finita de modelos / complexidade descritiva, então significará "primeira ordem sobre palavras binárias finitas, usando os predicados Rs e um predicado unário P verdadeiro na posição do 1 na palavra".$FO(R)$

Gostaria de saber, existe alguma caracterização de com R algum predicado em N r para alguns r? Por exemplo, em F O ( < , + ) ou F O ( < , P 2 ) em que P 2 é o conjunto de potências de 2. Especialmente, parece-me que deve ser igual a A C 0 com alguma condição de uniformidade , mas não consigo encontrar nenhum resultado que afirme isso.$FO(<,R)$$\mathbb N^r$$FO(<,+)$$FO(<,P_2)$$P_2$$AC^0$

Aqui está o que eu já sei, para algum valor de .$R$

É bem sabido que , a lógica de primeira ordem de palavras com um fim e um predicado bit é igual a A C 0 - F O ( < , b i t ) uniforme. Com isso, os dois reconhecem exatamente os mesmos idiomas. Veja, por exemplo, "Complexidade descritiva" de Immerman, página 82. (Também é igual a muitas outras caracterizações, como A C 0 - tempo de log uniforme e máquina de acesso aleatório paralelo em tempo constante, mas não é o que sou. procurando aqui.)$FO(<,bit)$$AC^0$$FO(<,bit)$$AC^0$

Se podemos usar predicado numérico arbitrário em nossa lógica de primeira ordem, então temos (não uniforme), se C é uma classe de função que contém a função computável em tempo de log, então F O ( < , C ) é igual a um C 0 - C -uniform (para estes dois resultados ver Barrington, " extensões de uma ideia de Mc-Naughton ", 1993).$AC^0$$C$$FO(<,C)$$AC^0-C$

Finalmente, é a classe da linguagem livre de estrela (linguagem que pode ser definida por uma expressão regular usando nenhuma estrela Kleene), mas isso não fornece informações em termos de complexidade do circuito.$FO(<)$

Não sei ao certo o que você está procurando, mas o seguinte pode ser interessante para você:

1. A idéia de que restringir predicados numéricos na fórmula FO corresponde a condições de uniformidade é explicitamente investigada, por exemplo, no artigo "FO (<) - uniformidade" de Behle e Lange.
2. A pesquisa "Aritmética, lógica de primeira ordem e quantificadores de contagem" de Schweikardt fornece uma visão geral dos resultados conhecidos sobre o poder expressivo de diferentes predicados aritméticos