Using confluence to generate rule-based constraint solvers
Slim Abdennadher, Christophe Rigotti · 2001
A general approach to implement propagation and simplification of constraints consists of applying rules over these constraints. Recently, several proposals have been made to solve finite constraint satisfaction problems by means of automatically generated propagation rules [4, 9, 3]. Since propagation rules do not rewrite constraints but add new ones, the constraint store may contain superfluous constraints. Removing these constraints not only allows saving of space but also decreases the cost of constraint solving. Constraints can be removed using simplification rules. In this paper, we present a method to transform propagation rules into simplification rules using the concept of confluence. The generated rules are implemented in the language Constraint Handling Rules (CHR). An example tak en from the field of digital circuit design shows that our approach is of practical use.