On the Strictness of the First-Order Quantifier Structure Hierarchy over Finite Structures

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.