Building Constraint Satisfaction Problem Solvers Using Rewrite Rules & Strategies

Carlos Castro 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we formalize Constraint Satisfaction Problem manipulation using a rule-based approach. Based on the notion of Computational Systems, we associate basic transformations carried out by traditional constraint solving algorithms with rewrite rules, and heuristics with strategies that establish the order of application of the inferences. In this way, a constraint solver can be viewed as a computational system aimed to transform a set of constraints in a particular solved form. The distinction made between deduction rules and strategies, allows to describe constraint handling in a very abstract way, prototype new heuristics almost by modifying only the choice of rules, prove termination in an easier way, and combine constraint solving with other computational systems. To validate our approach we have implemented the system COLETTE, which is currently executable in ELAN, an environment for prototyping computational systems. We have realized how easy it is to integrate and reuse solvers developed following this approach. We hope that this work leads the way to the integration, in each other, of the knowledge existing in the domains of Automated Deduction and Constraint Solving.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 1998, 34 (3), pp.263-293
Liste complète des métadonnées

https://hal.inria.fr/inria-00098517
Contributeur : Publications Loria <>
Soumis le : lundi 25 septembre 2006 - 17:03:05
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58

Identifiants

  • HAL Id : inria-00098517, version 1

Collections

Citation

Carlos Castro. Building Constraint Satisfaction Problem Solvers Using Rewrite Rules & Strategies. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 1998, 34 (3), pp.263-293. 〈inria-00098517〉

Partager

Métriques

Consultations de la notice

214