FO-uniform AC0 z pewnym orzeczeniem

9

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 Nrdla jakiegoś r? Na przykład naFO(<,+)lub FO(<,P2) gdzie P2 jest zbiorem potęgi 2. Szczególnie wydaje mi się, że powinna być równa AC0 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 AC0-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 jakAC0-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 AC0 (niejednolity), jeśli C jest klasą funkcji zawierającą funkcję obliczalną w czasie dziennika FO(<,C) jest równe AC0C-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.

Arthur MILCHIOR
źródło

Odpowiedzi:

5

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
fh
źródło
Dziękuję bardzo, pierwszy z tych dwóch artykułów był dokładnie tym, czego szukałem. Udowodniłem część jego wyniku i byłem prawie pewien, że ktoś już to udowodnił, ponieważ dowód jest prawie taki sam jak dowód o jednorodności FO (<, nieco).
Arthur MILCHIOR