Generating propagators for finite set constraints
2006 (English)In: Principles And Practice Of Constraint Programming - CP 2006 / [ed] Benhamou, F, 2006, Vol. 4204, 575-589 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
2006. Vol. 4204, 575-589 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 4204
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-42006ISI: 000241582400040ScopusID: 2-s2.0-33750366714ISBN: 3-540-46267-8OAI: oai:DiVA.org:kth-42006DiVA: diva2:445864
12th International Conference on Principles and Practice of Constraint Programming, CP 2006; Nantes; 25 September 2006 through 29 September 2006
QC 201110052011-10-052011-10-052011-10-05Bibliographically approved