Computer Science – Performance
Scientific paper
2000-12-15
Computer Science
Performance
35 pages. To appear in ACM TOPLAS
Scientific paper
Constraint propagation algorithms form an important part of most of the constraint programming systems. We provide here a simple, yet very general framework that allows us to explain several constraint propagation algorithms in a systematic way. In this framework we proceed in two steps. First, we introduce a generic iteration algorithm on partial orderings and prove its correctness in an abstract setting. Then we instantiate this algorithm with specific partial orderings and functions to obtain specific constraint propagation algorithms. In particular, using the notions commutativity and semi-commutativity, we show that the {\tt AC-3}, {\tt PC-2}, {\tt DAC} and {\tt DPC} algorithms for achieving (directional) arc consistency and (directional) path consistency are instances of a single generic algorithm. The work reported here extends and simplifies that of Apt \citeyear{Apt99b}.
No associations
LandOfFree
The Role of Commutativity in Constraint Propagation Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Role of Commutativity in Constraint Propagation Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Role of Commutativity in Constraint Propagation Algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-510583