Computing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems

Computer Science – Programming Languages

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-459270

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.