Interval propagation to reason about sets: Definition and implementation of a practical language

Local consistency techniques have been introduced in logic programming in order to extend the application domain of logic programming languages The existing languages based on these techniques consider arithmetic constraints applied to variables ranging over nite integer domains This makes di cult a natural and concise modelling as well as an e cient solving of a class of NP complete combinatorial search problems dealing with sets To overcome these problems we propose a solution which consists in extending the notion of integer domains to that of set domains sets of sets We specify a set domain by an interval whose lower and upper bounds are known sets ordered by set inclusion We de ne the formal and practical framework of a new constraint logic programming language over set domains called Conjunto Conjunto comprises the usual set operation symbols n and the set inclusion relation Set expressions built using the operation symbols are interpreted as relations s s s provides us with a set of constraints called graduated constraints e g the set cardinality which map sets onto arithmetic terms This allows us to handle optimization problems by applying a cost function to the quanti able i e arithmetic terms which are associated to set terms The constraint solving in Conjunto is based on local consistency techniques using interval reasoning which are extended to handle set constraints The main contribution of this paper concerns the formal de nition of the language and its design and implementation as a practical language