
FCT 2009
17th International Symposium on Fundamentals of Computation Theory
September 24, 2009, Wrocław, Poland
August 31, Wroclaw University, room 119

11^{15}13^{00}
Manuel Bodirsky, Ecole Polytechnique, France,
Introduction to Constraint Satisfaction Complexity and Applications in Spatial and Temporal Reasoning
Abstract.
The constraint satisfaction framework is known to be sufficiently
rich and expressive for representing problems occurring in a wide
variety of industrial and scientific applications. This has led to
the development of constraint programming languages and very
successful commercial constraint solvers.
Qualitative temporal and spatial reasoning is a wellestablished area
in artificial intelligence. The computational complexity of various
reasoning tasks has been a central topic in this area, and there are
many surprisingly rich formalisms where reasoning is polynomialtime
tractable.
We apply techniques from constraint satisfaction complexity to give
systematic complexity results for temporal and spatial reasoning
formalisms. In particular, we use the socalled universalalgebraic
approach that was originally developed for finite domain constraint
satisfaction problems, and generalize it to study infinite domain
constraint satisfaction problems.
September 1, Wroclaw University, room 119

16^{15}18^{00}
Manuel Bodirsky, Ecole Polytechnique, France,
On the scope of the universalalgebraic approach to constraint satisfaction
Abstract.
The universalalgebraic approach is a powerful tool to study
the computational complexity of constraint satisfaction problems (CSPs).
It rests on the observation that a relation has a primitive positive
definition in a finite
structure if and only if the relation is preserved by all
polymorphisms of the structure.
This correspondence between primitive positive definability and
polymorphisms
also holds for infinite omegacategorical structures.
In this talk, I present an elegant necessary and sufficient condition
that
characterizes whether a CSP can be formulated
with an omegacategorical template.
Then we show that for every structure A there exists a structure B
that has the same CSP as A
such that a firstorder definable relation R is primitive positive
definable
in B if and only if R is preserved by all infinitary polymorphisms of B.
This shows that polymorphisms can be used
to study the computational complexity of CSPs with arbitrary infinite
templates.
I present several applications of this paradigm; for example, a
characterization of those infinite domain CSPs that are in the
complexity class FO.
