A Logic that Captures βP on Ordered Structures

Studies in Logic, Vol. 13, No. 3 (2020): 01–18 PII: 1674-3202(2020)-03-00001-18
Kexu Wang          Xishun Zhao

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 ∃logωIFP captures the limited nondeterminism class β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 in the general case, i.e., on all the finite structures.