Manuel Bodirsky - Cores of Countably Categorical Structures

lmcs:2224 - Logical Methods in Computer Science, January 25, 2007, Volume 3, Issue 1 - https://doi.org/10.2168/LMCS-3(1:2)2007
Cores of Countably Categorical StructuresArticle

Authors: Manuel Bodirsky ORCID

    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.


    Volume: Volume 3, Issue 1
    Published on: January 25, 2007
    Submitted on: September 23, 2005
    Keywords: Computer Science - Logic in Computer Science,F.4.1

    34 Documents citing this article

    Consultation statistics

    This page has been seen 978 times.
    This article's PDF has been downloaded 268 times.