The core of a countably categorical structure
Please always quote using this URN:urn:nbn:de:0296-matheon-2754
- A relational structure is a core, if all its endomorphisms are embeddings. This notion is important for the classification for the computational complexity of constraint satisfaction problems. It is a fundamental fact that every finite structure S has a core, i.e., S has an endomorphism e such that the structure induced by e(S) is a core; moreover, the core is unique up to isomorphism. We prove that this result remains valid for countably categorical structures, and prove that every countably categorical structure has a core, which is unique up to isomorphism, and which is again countably categorical. We thus reduced the classification for the complexity of constraint satisfaction problems with countably categorical templates to the classifiaction for constraint satisfaction problems where the templates are countably categorical cores. We also show that a core of a countably categorical structure Gamma is model complete, and therefore universal-existential axiomatizable. If Gamma contains all primitive positive definable relations, then the core of Gamma admits quantifier elimination. We discuss consequences for constraint satisfaction with countably categorical templates.
Author: | Manuel Bodirsky |
---|---|
URN: | urn:nbn:de:0296-matheon-2754 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2005/05/11 |
Release Date: | 2005/10/31 |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 281 |