Chen, Hubie and Müller, Moritz - 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
An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction

Authors: Chen, Hubie and Müller, Moritz

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.


Source : oai:arXiv.org:1207.6696
DOI : 10.2168/LMCS-9(1:15)2013
Volume: Volume 9, Issue 1
Published on: March 29, 2013
Submitted on: August 8, 2012
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Logic


Share

Consultation statistics

This page has been seen 46 times.
This article's PDF has been downloaded 6 times.