When do bounds and domain propagation lead to the same search space

Christian Schulte, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

12 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationProceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming
PublisherAssociation for Computing Machinery (ACM)
Pages115-126
Number of pages12
ISBN (Print)158113388X, 9781581133882
Publication statusPublished - 1 Jan 2001
EventInternational ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2001) - Florence, Italy
Duration: 5 Sep 20017 Sep 2001
Conference number: 3rd

Publication series

NameProceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming

Conference

ConferenceInternational ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2001)
CountryItaly
CityFlorence
Period5/09/017/09/01

Keywords

  • Abstract interpretation
  • Bounds propagation
  • Constraint (logic) programming
  • Domain propagation
  • Finite domain constraints
  • Program analysis

Cite this