Cores of countably categorical structures
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 1–16 |
Fachzeitschrift | Logical methods in computer science |
Jahrgang | 3 |
Ausgabenummer | 1 |
Publikationsstatus | Veröffentlicht - 25 Jan. 2007 |
Peer-Review-Status | Ja |
Extern publiziert | Ja |
Externe IDs
Scopus | 76849101459 |
---|---|
ORCID | /0000-0001-8228-3611/work/142241158 |
Schlagworte
Schlagwörter
- Constraint satisfaction, Cores, ω-categorical structures