Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language - Université de Montpellier Accéder directement au contenu
Article Dans Une Revue Constraints Année : 1997

Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language

Résumé

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 finite integer domains. This makes difficult a natural and concise modelling as well as an efficient solving of a class of N P-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 define 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 1 = s 2 ,...). In addition, Conjunto 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 quantiiable, 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 deenition of the language and its design and implementation as a practical language.
Fichier principal
Vignette du fichier
Gervet97-preprint.pdf (509.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01742403 , version 1 (24-03-2018)

Identifiants

Citer

Carmen Gervet. Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language. Constraints, 1997, ⟨10.1007/BF00137870⟩. ⟨hal-01742403⟩
184 Consultations
497 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More