×

Generating propagators for finite set constraints. (English) Zbl 1160.68387

Benhamou, Frédéric (ed.), Principles and practice of constraint programming – CP 2006. 12th international conference, CP 2006, Nantes, France, September 25–29, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-46267-5/pbk). Lecture Notes in Computer Science 4204, 575-589 (2006).
Summary: 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.
For the entire collection see [Zbl 1141.68004].

MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI