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

Simple item page
dc.creatorvan Emden, M. H.
dc.date2001-06-07
dc.date.accessioned2026-07-07T03:17:12Z
dc.date.available2026-07-07T03:17:12Z
dc.descriptionBox 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.
dc.descriptionPresented at the Sixth Annual Workshop of the ERCIM Working Group on Constraints. 12 pages
dc.identifierhttps://arxiv.org/abs/cs/0106008
dc.identifierhttp://arxiv.org/abs/cs/0106008
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30631
dc.subjectProgramming Languages
dc.subjectArtificial Intelligence
dc.subjectD.3.2; D.3.3; F.4.1
dc.titleComputing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems
dc.typetext

Files

Collections

arXiv