Hubie Chen ; Moritz Müller - An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction

lmcs:1009 - Logical Methods in Computer Science, March 29, 2013, Volume 9, Issue 1 - https://doi.org/10.2168/LMCS-9(1:15)2013
An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint SatisfactionArticle

Authors: Hubie Chen ; Moritz Müller

    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.


    Volume: Volume 9, Issue 1
    Published on: March 29, 2013
    Imported on: August 8, 2012
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Logic

    1 Document citing this article

    Consultation statistics

    This page has been seen 2512 times.
    This article's PDF has been downloaded 270 times.