Predicting Derivation Lengths in Rule-based Constraint Programs.
Thom Frühwirth · JFPLC · 2000
We automatically 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. 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. We apply our method to constraint solvers ranging from Boolean and arithmetic to terminological and path-consistent constraints. In most cases, the worst-case derivation length is linear in the syntactic size of the constraint problem. RESUME. Nous prevoyons automatiquement le nombre maximal d’application de regles (c.-a.d. longueur de derivation dans les pires des cas) dans des solveur de contraintes bases sur des regles ecrits dans le langage CHR. Les longueurs de derivation sont derivees a partir des rangs utilises dans des preuves de terminaison pour ces programmes. Nous sommes particulierement interesses par les rangs qui nous donnent une bonne limite superieure. Nous appliquons notre methode sur des differents solveurs de contraintes, tels que contraintes booleennes, equations lineaires et contraintes terminologiques. Dans la plupart des cas, la longueur de derivation (dans les pires des cas) est lineaire dans la taille syntactique du probleme.