FO-форма AC0 с некоторым предикатом

Мой вопрос касается теории конечных моделей / описательной сложности, поэтому будет означать «первый порядок по конечным двоичным словам с использованием предикатов Rs и унарного предиката P true в позиции 1 в слове».$FO(R)$

Я хотел бы знать, есть ли какая-либо характеристика с R любым предикатом на для некоторого r? Например, для или где - это набор 2. Особенно мне кажется, что он должен быть равен с некоторым условием равномерности, но я могу не найти никакого результата, который утверждает это.$FO(<,R)$$\mathbb N^r$$FO(<,+)$$FO(<,P_2)$$P_2$$AC^0$

Вот то , что я уже знаю, при некотором значении .$R$

Хорошо известно, что , логика первого порядка для слов с порядком и битовым предикатом, равна - равномерно. Это означает, что они оба распознают одни и те же языки. См., Например, «Описательная сложность» Иммермана, стр. 82. (Он также равен многим другим характеристикам, таким как униформа времени и машина параллельного произвольного доступа с постоянным временем, но это не то, чем я являюсь ищу здесь.)$FO(<,bit)$$AC^0$$FO(<,bit)$$AC^0$

Если мы можем использовать произвольный числовой предикат в нашей логике первого порядка, то мы имеем (неоднородный), если является классом функции, содержащей вычислимую функцию времени журнала, то равен равномерный (для этих двух результатов см. Баррингтон, " Расширения идеи Мак-Нотона ", 1993).$AC^0$$C$$FO(<,C)$$AC^0-C$

Наконец, - это класс беззвездного языка (язык, который можно определить с помощью регулярного выражения, не использующего звезду Клини), но это не дает никакой информации с точки зрения сложности схемы.$FO(<)$

Я не совсем уверен, что вы ищете, но вам может быть интересно следующее:

1. Идея о том, что ограничение числовых предикатов в FO-формуле соответствует условиям равномерности, подробно исследована, например, в статье «FO (<) - равномерность» Беле и Ланге.
2. Опрос Schweikardt «Арифметика, логика первого порядка и счетные квантификаторы» дает обзор известных результатов об выразительной силе различных арифметических предикатов.