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

9

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

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

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

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

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

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

Артур МИЛКИОР
источник

Ответы:

5

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

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