When do bounds and domain propagation lead to the same search space?
2005 (English)In: ACM Transactions on Programming Languages and Systems, ISSN 0164-0925, E-ISSN 1558-4593, Vol. 27, no 3, 388-425 p.Article in journal (Refereed) Published
This article explores the question of when two propagation-based constraint systems have the same behavior, in terms of search space. We categorize the behavior of domain and bounds propagators for primitive constraints, and provide theorems that allow us to determine propagation behaviors for conjunctions of constraints. We then show how we can use this to analyze CLP(FD) programs to determine when we can safely replace domain propagators by more efficient bounds propagators without increasing search space. Empirical evaluation shows that programs optimized by the analysis' results are considerably more efficient.
Place, publisher, year, edition, pages
2005. Vol. 27, no 3, 388-425 p.
constraint (logic) programming, finite domain constraints, bounds propagation, domain propagation, abstract interpretation, program analysis, logic programs, constraint
IdentifiersURN: urn:nbn:se:kth:diva-14844DOI: 10.1145/1065887.1065889ISI: 000229934700002ScopusID: 2-s2.0-33745348779OAI: oai:DiVA.org:kth-14844DiVA: diva2:332885
QC 20100525 QC 201201312010-08-052010-08-052012-01-31Bibliographically approved