On the Strictness of the First-Order Quantifier Structure Hierarchy over Finite Structures
Yuguo He · 2010
One of the major interests of finite model theory is to separate the expressive power of different logics or fragments of logics. In this paper, we define a variant of Ehrenfeucht-Fraïssé games that characterizes quantifier classes over finite structures and prove that the fragments of first-order logic based on quantifier structures form a strict hierarchy in terms of their expressiveness over finite structures.