Logarithmic-Bounded Second-Order Quantifiers and Limited Nondeterminism.
Kexu Wang, Xishun Zhao · arXiv (Cornell University) · 2019
We add logarithmic-bounded second-order quantifiers to the inflationary fixed-point logic, and find on ordered structures the new logic $\exists^{\log^{\omega}}\text{IFP}$ captures the limited nondeterminism class $\beta\text{P}$. A new version of Ehrenfeucht-Fraisse game for the new logic is also designed in order to study its expressive power.