Publication details

Saarland University Computer Science

Promoting Constraints to First-class Status

Tobias Müller

Proceedings of the First International Conference on Computational Logic -- CL2000, Vol. 1861 of lnai, pp. 429--447, springer, July 2000

This paper proposes to promote constraints to first-class status. In contrast to constraint propagation, which performs inference on values of variables, first-class constraints allow reasoning about the constraints themselves. This lets the programmer access the current state of a constraint and control a constraint's behavior directly, thus making powerful new programming and inference techniques possible, as the combination of constraint propagation and rewriting constraints `a la term rewriting. First-class constraints allow for em true meta constraint programming. Promising applications in the field of combinatorial optimization include early unsatisfiability detection, constraint reformulation to improve propagation, garbage collection of redundant but not yet entailed constraints, and finding minimal inconsistent subsets of a given set of constraints for debugging immediately failing constraint programs.
We demonstrate the above-mentioned applications by means of examples. The experiments were done with Mozart Oz but can be easily ported to other constraint solvers.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009