Titre :  Distance Constraint Satisfaction Problems

Exposant : Barnaby Martin

Résumé : Infinite-domain Constraint Satisfaction Problems (CSPs) are by now a
well-established research area. Perhaps surprisingly, it is only
relatively recently that the structure of the integers has been
considered for classes of template. While rationals model continuous
time, integers model discrete time - though their additional structure
typically introduces both complexity and complications. We will survey
known results, especially for (Z;succ) as well as semilinear integer
languages. Although less benign than the rationals, the integers
maintain very basic structure, and we will consider the ways,
model-theoretic and combinatorial, that this may be exploited in the
search for complexity classifications.