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

Christian Schulte; Peter J. Stuckey

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

Christian Schulte, Peter J. Stuckey

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

13 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 language	English
Title of host publication	Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming
Publisher	Association for Computing Machinery (ACM)
Pages	115-126
Number of pages	12
ISBN (Print)	158113388X, 9781581133882
Publication status	Published - 1 Jan 2001
Event	International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2001) - Florence, Italy Duration: 5 Sep 2001 → 7 Sep 2001 Conference number: 3rd

Publication series

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

Conference

Conference	International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2001)
Country/Territory	Italy
City	Florence
Period	5/09/01 → 7/09/01

Keywords

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

Cite this

Schulte, C., & Stuckey, P. J. (2001). When do bounds and domain propagation lead to the same search space. In Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (pp. 115-126). (Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming). Association for Computing Machinery (ACM).

Schulte, Christian ; Stuckey, Peter J. / When do bounds and domain propagation lead to the same search space. Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. Association for Computing Machinery (ACM), 2001. pp. 115-126 (Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming).

@inproceedings{2d273e4561df4c7cb726e97df6ba61e6,

title = "When do bounds and domain propagation lead to the same search space",

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.",

keywords = "Abstract interpretation, Bounds propagation, Constraint (logic) programming, Domain propagation, Finite domain constraints, Program analysis",

author = "Christian Schulte and Stuckey, {Peter J.}",

year = "2001",

month = jan,

day = "1",

language = "English",

isbn = "158113388X",

series = "Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming",

publisher = "Association for Computing Machinery (ACM)",

pages = "115--126",

booktitle = "Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming",

address = "United States of America",

note = "International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2001) ; Conference date: 05-09-2001 Through 07-09-2001",

}

Schulte, C & Stuckey, PJ 2001, When do bounds and domain propagation lead to the same search space. in Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, Association for Computing Machinery (ACM), pp. 115-126, International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2001), Florence, Italy, 5/09/01.

When do bounds and domain propagation lead to the same search space. / Schulte, Christian; Stuckey, Peter J.

Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. Association for Computing Machinery (ACM), 2001. p. 115-126 (Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

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

AU - Schulte, Christian

AU - Stuckey, Peter J.

N1 - Conference code: 3rd

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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.

AB - 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.

KW - Abstract interpretation

KW - Bounds propagation

KW - Constraint (logic) programming

KW - Domain propagation

KW - Finite domain constraints

KW - Program analysis

UR - http://www.scopus.com/inward/record.url?scp=0035790267&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:0035790267

SN - 158113388X

SN - 9781581133882

T3 - Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming

SP - 115

EP - 126

BT - Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming

PB - Association for Computing Machinery (ACM)

T2 - International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2001)

Y2 - 5 September 2001 through 7 September 2001

ER -

Schulte C, Stuckey PJ. When do bounds and domain propagation lead to the same search space. In Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. Association for Computing Machinery (ACM). 2001. p. 115-126. (Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming).

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

Abstract

Publication series

Conference

Keywords

Other files and links

Cite this