## Negation in Combining Constraint Systems

**Stephan Kepser**
*To appear in Frontiers of Combining Systems, Proceedings 98. Maarten
de Rijke and Dov Gabbay (Eds.). Kluwer Academic Publishers, 1998.*

In a recent paper, Baader and Schulz presented a general method for
the combination of constraint systems for purely positive
constraints.
But negation plays an important role in constraint
solving. E.g., it is vital for constraint entailment.
Therefore it is of interest to extend their results to the
combination of constraint problems containing negative constraints.
We show that the combined solution domain introduced by Baader and
Schulz is a domain in which one can solve positive and negative
``mixed'' constraints by presenting an
algorithm that reduces solvability of positive and negative ``mixed''
constraints to solvability of pure constraints in the components.
The existential theory in the combined solution domain is decidable
if solvability of literals with so-called linear constant
restrictions is decidable in the components.
We also give a criterion for ground solvability of mixed constraints
in the combined solution domain.
The handling of negative constraints can be significantly simplified
if one can show that the solution domain owns the independence of
negative constraints property.
We provide a modularity result giving sufficient conditions for the
component systems in order for the combined solution
domain to have the independence property.