Generating Propagators for Finite Set Constraints
Guido Tack, Christian Schulte, Gert Smolka.
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 run-time analysis, including techniques for efficiently executing projectors for n-ary constraints.
In: Frédéric Benhamou, editor, Twelfth International Conference on Principles and Practice of Constraint Programming, Nantes, France, volume 4204 of Lecture Notes in Computer Science, pages 575-589. Springer-Verlag, September, 2006. DOI 10.1007/11889205_41.
Copyright Springer-Verlag, the original publication is available at www.springerlink.com