CSPs in ultrametric spaces
Martin Hils, University Paris 7, Equipe Logique Mathematique

        
CSPs in (the Fraisse limit of all finite) ultrametric
spaces reduce to questions on the distances between the points
and balls which are involved. We give an elementary construction
(called pp-presentation), which is more general than pp-interpretations,
and which provides such a reduction. Some interesting structures are
reducts of ultrametric spaces, e.g. the one given by the (dense and
everywhere infinitely branching) C-relation. PP-presentations can for instance be used to reduce the CSP for the C-relation to a CSP over the dense linear order that is known to be polynomial-time tractable.