An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified   Constraint Satisfaction
  We prove an algebraic preservation theorem for positive Horn definability in aleph-zero categorical structures. In particular, we define and study a construction which we call the periodic power of a structure, and define a periomorphism of a structure to be a homomorphism from the periodic power of the structure to the structure itself. Our preservation theorem states that, over an aleph-zero categorical structure, a relation is positive Horn definable if and only if it is preserved by all periomorphisms of the structure. We give applications of this theorem, including a new proof of the known complexity classification of quantified constraint satisfaction on equality templates. 
Hubie Chen (Univ. Pompeu Fabra), Moritz M\"uller (Kurt G\"odel   Research Center, Universit\"at Wien)
cs.LO cs.CC math.LO