Integration and Optimization of Rule-based Constraint Solvers

by Slim Abdennadher and Thom Fruehwirth

Abstract:

 	One lesson learned from practical applications is that constraintsare often heterogeneous. 
 Solving such constraints requires a collaboration of constraint solvers. In this paper, we introduce a
 methodology for the tight integration of \chr\ constraint programs into one such program.  
 	CHR is a high-level rule-based language for writing constraint solvers and reasoning systems.  A constraint  
 solver is well-behaved if it is terminating and confluent. When merging constraint solvers, this property 
 may be lost. Based on previous results on CHR program analysis and transformation we show  how to utilize 
 completion to regain well-behavedness. We identify a class of solvers whose union is always confluent and 
 we show that for preserving termination such a class is hard to find.
 	The merged and completed constraint solvers may contain redundant rules. Utilizing the notion of 
 operational equivalence, which is decidable for well-behaved CHR programs, we present a method to detect 
 redundant rules in a CHR program.