Please use this identifier to cite or link to this item:
doi:10.22028/D291-25783
Title: | When do bounds and domain propagation lead to the same search space |
Author(s): | Schulte, Christian Stuckey, Peter J. |
Language: | English |
Year of Publication: | 2001 |
OPUS Source: | Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, Florence, Italy, September 5-7, 2001. - New York: ACM Press, 2001, pp. 115-126. |
SWD key words: | Constraint-logische Programmierung |
Free key words: | Constraints |
DDC notations: | 004 Computer science, internet |
Publikation type: | Conference Paper |
Abstract: | This paper explores the question of when two propagation-based constraint systems have the same behaviour, in terms of search space. We categorise the behaviour of domain and bounds propagators for primitive constraints, and provide theorems that allow us to determine propagation behaviours for conjunctions of constraints. We then show how we can use this to analyse CLP(FD) programs to determine when we can safely replace domain propagators by more efficient bounds propagators without increasing search space. |
Link to this record: | urn:nbn:de:bsz:291-scidok-3052 hdl:20.500.11880/25839 http://dx.doi.org/10.22028/D291-25783 |
Date of registration: | 13-Jul-2004 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
SchulteStuckey-PPDP2.pdf | 246,17 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.