Mathematics – Logic
Scientific paper
2011-05-30
Mathematics
Logic
29 pages
Scientific paper
One way of studying a relational structure is to investigate functions which are related to that structure and which leave certain aspects of the structure invariant. Examples are the automorphism group, the self-embedding monoid, the endomorphism monoid, or the polymorphism clone of a structure. Such functions can be particularly well understood when the relational structure is countably infinite and has a first-order definition in another relational structure which has a finite language, is totally ordered and homogeneous, and has the Ramsey property. This is because in this situation, Ramsey theory provides the combinatorial tool for analyzing these functions -- in a certain sense, it allows to represent such functions by functions on finite sets. This is a survey of results in model theory and theoretical computer science obtained recently by the authors in this context. In model theory, we approach the problem of classifying the reducts of countably infinite ordered homogeneous Ramsey structures in a finite language, and certain decidability questions connected with such reducts. In theoretical computer science, we use the same combinatorial methods in order to classify the computational complexity for various classes of infinite-domain constraint satisfaction problems. While the first set of applications is obviously of an infinitary character, the second set concerns genuinely finitary problems -- their unifying feature is that the same tools from Ramsey theory are used in their solution.
Bodirsky Manuel
Pinsker Michael
No associations
LandOfFree
Reducts of Ramsey 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 Reducts of Ramsey structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducts of Ramsey structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-679026