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

Kexu Wang, Xishun Zhao

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 log…