Cores of Countably Categorical Structures

Details Cores of Countably Categorical Structures Cores of Countably Categorical Structures

2006-12-13

arxiv.org/abs/cs/0612069v2

LMCS 3 (1:2) 2007

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-3(1:2)2007

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.

Affiliated with

Also associated with

No associations

Rating

Cores of Countably Categorical Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cores of Countably Categorical Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cores of Countably Categorical Structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-585332