We investigate a class of set constraints that is used for the type analysis of concurrent
constraint programs. Its constraints are inclusions between first-order terms (without set
operators) interpreted over non-empty sets of finite trees. We show that this class has the
independence property. We give a polynomial algorithm for entailment. The independence
property is a fundamental property of constraint systems. It says that the constraints cannot
express disjunctions, or, equivalently, that negated conjuncts are independent from each …

We investigate a class of set constraints that is used for the type analysis of concurrent
constraint programs. Its constraints are inclusions between rst-order terms (without set
operators) interpreted over non-empty sets of nite trees. We show that this class has the
independence property. We give a polynomial algorithm for entailment. The independence
property is a fundamental property of constraint systems. It says that the constraints cannot
express disjunctions, or, equivalently, that negated conjuncts are independent from each …