Cores of Countably Categorical Structures
Cores of Countably Categorical Structures
复制标题
可数范畴结构的核心
DOI：
10.2168/lmcs-3(1:2)2007
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
M. Bodirsky
中科院分区：
文献类型：
--
作者：
M. Bodirsky
一个关系结构是一个核，如果它的所有自同态都是嵌入。这一概念对于约束满足问题的计算复杂性分类是非常重要的。一个基本的事实是，每个有限结构都有一个核，即，有一个自同态，使得由它的图像诱导的结构是一个核心;而且，核心是唯一的同构。我们证明了每一个\omega -范畴结构都有一个核。此外，每个\omega-范畴结构同态等价于一个模型完备核，该核在同构之前是唯一的，并且是有限的或\omega -范畴的。我们讨论的后果约束满足\omega -分类模板。
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.