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

This page has been seen 59 times.

This article's PDF has been downloaded 8 times.