首页    期刊浏览 2024年11月26日 星期二
登录注册

文章基本信息

  • 标题:Cores of Countably Categorical Structures
  • 本地全文:下载
  • 作者:Manuel Bodirsky
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2007
  • 卷号:3
  • 期号:01
  • DOI:10.2168/LMCS-3(1:2)2007
  • 出版社:Technical University of Braunschweig
  • 摘要:

    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 ?-categorical structure has a core. Moreover, every ?-categorical structure is homomorphically equivalent to a model-complete core, which is unique up to isomorphism, and which is finite or ?-categorical. We discuss consequences for constraint satisfaction with ?-categorical templates.

  • 关键词:Categorical Structures;Relational structures;Computational Complexity;Constraint Satisfaction;Endomorphisms
国家哲学社会科学文献中心版权所有