Logical Methods in Computer Science. DOI: 10.2168/LMCS-3(1:2). An extended abstract of this paper appeared in the proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science, Stuttgart, pages 110-120, LNCS 3404.
A relational structure is a core, if all its endomorphisms are embeddings. This notion is important for computational complexity classification of constraint satisfaction problems. It is a fundamental fact that every finite structure S has a core, i.e., S has an endomorphism e such that the structure induced by e(S) is a core; moreover, the core is unique up to isomorphism. We prove that every countably categorical structure has a core. Moreover, every countably categorical structure is homomorphically equivalent to a model-complete core, which is unique up to isomorphism, and which is finite or countably categorical. We discuss consequences for constraint satisfaction with countably categorical templates. This is an extended and corrected version of a conference paper that appeared in STACS'05.
Document available online from LMCS
The slides of a talk on constraint satisfaction problems with infinite domains, in Postscript