AN ALGEBRAIC PRESERVATION THEOREM FOR N-0-CATEGORICAL QUANTIFIED CONSTRAINT SATISFACTION

作者：Chen Hubie^*; Mueller Moritz

来源：Logical Methods in Computer Science, 2013, 9(1): 15.

DOI：10.2168/LMCS-9(1:15)2013

• algebraic preservation theorem
• quantified constraint satisfaction
• polymorphisms
• complexity classification

We prove an algebraic preservation theorem for positive Horn definability in N-0-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 N-0-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.

• 出版日期2013