TY - GEN A1 - Bodirsky, Manuel T1 - Constraint Satisfaction with Infinite Domains N2 - Many constraint satisfaction problems have a natural formulation as a homomorphism problem. For a fixed relational structure Gamma we consider the following computational problem: Given a structure S with the same relational signature as Gamma, is there a homomorphism from S to Gamma? This problem is known as the constraint satisfaction problem CSP(Gamma) for the so-called template Gamma and is intensively studied for relational structures Gamma with a finite domain. However, many constraint satisfaction problems can not be formulated with a finite template. If we allow arbitrary infinite templates, constraint satisfaction is very expressive. We show that it contains undecidable problems, even if the constraint language is binary. In general, a computational problem can be described as the constraint satisfaction problem of an infinite template if and only if it is closed under inverse homomorphisms and disjoint unions. It is also easy to see that we can restrict our attention to countable templates. In this thesis we study the computational complexity of constraint satisfaction with templates that are omega-categorical. A structure Gamma is omega-categorical if all countable models of the first-order theory of Gamma are isomorphic to Gamma. This concept is central and well-studied in model-theory. On the one hand, omega-categoricity is a rather strong model-theoretic assumption on a relational structure, and we can use them to show that many techniques for constraint satisfaction with finite templates extend to omega-categorical templates. Y1 - 2005 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/285 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-2852 ER -