  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.

Programming Languages;Artificial Intelligence