Cores of countably categorical structures

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

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., an endomorphism such that the structure induced by its image is a core; moreover, the core is unique up to isomorphism. We prove 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.

Details

Original languageEnglish
Pages (from-to)1–16
JournalLogical methods in computer science
Volume3
Issue number1
Publication statusPublished - 25 Jan 2007
Peer-reviewedYes
Externally publishedYes

External IDs

Scopus 76849101459
ORCID /0000-0001-8228-3611/work/142241158

Keywords

Keywords

  • Constraint satisfaction, Cores, ω-categorical structures