Logarithmic-Bounded Second-Order Quantifiers and Limited Nondeterminism
share
We add logarithmic-bounded second-order quantifiers to the inflationary fixed-point logic, and find on ordered structures the new logic ∃^log^ωIFP captures the limited nondeterminism class βP. A new version of Ehrenfeucht-Fraisse game for the new logic is also designed in order to study its expressive power.
READ FULL TEXT