Henkin quantifiers: logic, games, and computation
Merlijn Sevenster

Abstract:
In this paper, we study the game-theoretic and computational repercussions
of Henkins partially ordered quantifiers. After defining a gametheoretic
semantics for these objects, we observe that tuning the parameter
of absentmindedness gives rise to quantifier prefixes studied. In the
interest of computation, we characterize the complexity class P_{||}^{NP}
in terms of partially ordered quantifiers, by means of a proof different from
Gottlob's. We conclude with some research questions at the interface of logic,
game theory, and complexity theory.