An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction
Data(s) |
07/02/2014
07/02/2014
29/03/2013
|
---|---|
Resumo |
23 p. -- An extended abstract of this work appears in the proceedings of the 2012 ACM/IEEE Symposium on Logic in Computer Science 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. |
Identificador |
Logical Methods in Computer Science 9(1) : (2013) // Article N. 15 1860-5974 10.2168/LMCS-9(1:15)2013 |
Idioma(s) |
eng |
Publicador |
Logical Methods in Computer Science c/o Institut f. Theoretische Informatik, Technische Universität Braunschweig |
Relação |
http://www.lmcs-online.org/ojs/viewarticle.php?id=1223&layout=abstract |
Direitos |
© H. Chen and M. Müller. This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Fra ncisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany info:eu-repo/semantics/openAccess |
Palavras-Chave | #algebraic preservation theorem #quantified constraint satisfaction #polymorphisms #complexity classification |
Tipo |
info:eu-repo/semantics/article |