Moje pytanie dotyczy teorii modeli skończonych / złożoności opisowej, więc 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 z R dowolnym orzeczeniem dla jakiegoś r? Na przykład nalub gdzie jest zbiorem potęgi 2. Szczególnie wydaje mi się, że powinna być równa z pewnymi warunkami jednolitości, ale nie mogę znaleźć żadnego wyniku, który by to stwierdził.
Oto, co już wiem, dla pewnej wartości .
Jak powszechnie wiadomo , logika pierwszego rzędu dla słów z porządkiem i predykatem bitowym jest równa -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 jak-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 (niejednolity), jeśli jest klasą funkcji zawierającą funkcję obliczalną w czasie dziennika jest równe -uniform (dla tych dwóch wyników patrz Barrington, „ Extensions of a Idea of Mc-Naughton ”, 1993).
Wreszcie 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.
źródło