Generating Propagators for Finite Set Constraints

Ideally, programming propagators as implementations of constraints should be
an entirely declarative process for a large class of constraints: a
high-level declarative specification is automatically translated into an
efficient propagator. 

This talk introduces the use of existential monadic second-order logic as
declarative specification language for finite set propagators. The approach
taken is to automatically derive projection propagators (involving a single
variable only) implementing constraints described by formulas. We show
soundness and completeness of the derived propagators and present a runtime
analysis, including techniques
for efficiently executing projectors for n-ary constraints. 

Joint work with: Guido Tack, Gert Smolka, Saarland U, Germany