Computer Science – Programming Languages
Scientific paper
2001-06-07
Computer Science
Programming Languages
Presented at the Sixth Annual Workshop of the ERCIM Working Group on Constraints. 12 pages
Scientific paper
Box consistency has been observed to yield exponentially better performance than chaotic constraint propagation in the interval constraint system obtained by decomposing the original expression into primitive constraints. The claim was made that the improvement is due to avoiding decomposition. In this paper we argue that the improvement is due to replacing chaotic iteration by a more structured alternative. To this end we distinguish the existing notion of box consistency from relational box consistency. We show that from a computational point of view it is important to maintain the functional structure in constraint systems that are associated with a system of equations. So far, it has only been considered computationally important that constraint propagation be fair. With the additional structure of functional constraint systems, one can define and implement computationally effective, structured, truncated constraint propagations. The existing algorithm for box consistency is one such. Our results suggest that there are others worth investigating.
No associations
LandOfFree
Computing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems 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 Computing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-459270