Publication details

Saarland University Computer Science

Generating Propagators for Finite Set Constraints

Guido Tack, Christian Schulte, Gert Smolka

12th International Conference on Principles and Practice of Constraint Programming, Vol. 4204 of Lecture Notes in Computer Science, pp. 575--589, Springer, 2006

Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically translated into an efficient propagator. This paper introduces the use of existential monadic second-order logic as declarative specification language for finite set propagators. The approach taken in the paper is to automatically derive projection propagators (involving a single variable only) implementing constraints described by formulas. By this, the paper transfers the ideas of indexicals to finite set constraints while considerably increasing the level of abstraction available with indexicals. The paper proves soundness and completeness of the derived propagators and presents a runtime analysis, including techniques for efficiently executing projectors for n-ary constraints.

Springer-Verlag, (Lecture Notes in Computer Science)

Download PDF        Show BibTeX               

Login to edit

Webmaster, Wed Sep 16 10:47:00 2009