1
FO-uniform AC0 z pewnym orzeczeniem
Moje pytanie dotyczy teorii modeli skończonych / złożoności opisowej, więc FO(R)FO(R)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)FO(<,R)FO(<,R) z R dowolnym orzeczeniem NrNr\mathbb N^rdla jakiegoś r? Na przykład …