Change search
ReferencesLink to record
Permanent link

Direct link
When do bounds and domain propagation lead to the same search space?
KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.ORCID iD: 0000-0002-6283-7004
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
Abstract [en]

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.
Keyword [en]
constraint (logic) programming, finite domain constraints, bounds propagation, domain propagation, abstract interpretation, program analysis, logic programs, constraint
National Category
Computer Science
URN: urn:nbn:se:kth:diva-14844DOI: 10.1145/1065887.1065889ISI: 000229934700002ScopusID: 2-s2.0-33745348779OAI: diva2:332885
QC 20100525 QC 20120131Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2012-01-31Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schulte, Christian
By organisation
Microelectronics and Information Technology, IMIT
In the same journal
ACM Transactions on Programming Languages and Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 26 hits
ReferencesLink to record
Permanent link

Direct link