Cores of Countably Categorical Structures
<|reference_start|>Cores of Countably Categorical Structures: 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 has a core, i.e., has an endomorphism such that the structure induced by its image is a core; moreover, the core is unique up to isomorphism. Weprove that every \omega -categorical structure has a core. Moreover, every \omega-categorical structure is homomorphically equivalent to a model-complete core, which is unique up to isomorphism, and which is finite or \omega -categorical. We discuss consequences for constraint satisfaction with \omega -categorical templates.<|reference_end|>
@article{bodirsky2006cores,
    title={Cores of Countably Categorical Structures},
    author={Manuel Bodirsky},
    journal={Logical Methods in Computer Science, Volume 3, Issue 1 (January
  25, 2007) lmcs:2224},
    year={2006},
    doi={10.2168/LMCS-3(1:2)2007},
    archivePrefix={arXiv},
    eprint={cs/0612069},
    primaryClass={cs.LO}
}