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
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 SizeFormat 
SchulteStuckey-PPDP2.pdf246,17 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.