A Logic that Captures $\beta$P on Ordered Structures

Abstract

We extend the inflationary fixed-point logic, IFP, with a new kind of second-order quantifiers which have (poly-)logarithmic bounds. We prove that on ordered structures the new logic ${\exists }^{{\log }^{\omega }}\text{IFP}$ captures the limited nondeterminism class $\beta \text{P}$. In order to study its expressive power, we also design a new version of Ehrenfeucht-Fraïssé game for this logic and show that our capturing result will not hold on the general case, i.e. on all the finite structures.

arXiv comment15 pages. This article was reported with a title "Logarithmic-Bounded Second-Order Quantifiers and Limited Nondeterminism" in National Conference on Modern Logic 2019, on November 9 in Beijing