On the Number of Rule Applications in Constraint Programs

AbstractWe predict the maximal number of rule applications, i.e. worst-case derivation lengths of computations, in rule-based constraint solver programs written in the CHR language. CHR are a committed-choice concurrent constraint logic programming language consisting of multi-headed guarded rules. The derivation lengths are derived from rankings used in termination proofs for the respective programs. We are especially interested in rankings that give us a good upper bound, we call such rankings tight. Based on test-runs with randomized data, we compare our predictions with empirical results by considering constraint solvers ranging from Boolean and terminological constraints to arc-consistency and path-consistency