Constraint Satisfaction with Infinite Domains

homomorphism problems.
These problems are specified by a structure T, called the
template, and the computational problem is to determine for a given
finite structure S of the same signature as T whether there is a
homomorphism from S to T. This problem is called the constraint
satisfaction problem for T, and was intensively studied for templates
T over a finite domain. It is possible to formalise many interesting
tractable, and many interesting hard problems in this way.

The guiding -- and mostly open -- research questions in this area
are:
- Which problems in this class are tractable, which problems are NP-hard?
- Are there problems that are of intermediate complexity?
- When are these problems tractable via constraint propagation?
- How can we determine the expressive power of the corresponding
constraint languages?
- Which computational problems can be formalised as homomorphism
problems?
- Which parts of the theory generalise to classes of infinite
templates?

I will give a survey on constraint satisfaction and techniques to
study the complexity of constraint satisfaction problems. Then, I
will report on some results that generalise these techniques to
infinite structures. This will be illustrated by problems that are
motivated in computational linguistics and bioinformatics.