Change search
ReferencesLink to record
Permanent link

Direct link
Generating propagators for finite set constraints
KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.ORCID iD: 0000-0002-6283-7004
2006 (English)In: Principles And Practice Of Constraint Programming - CP 2006 / [ed] Benhamou, F, 2006, Vol. 4204, 575-589 p.Conference paper (Refereed)
Abstract [en]

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
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-42006ISI: 000241582400040ScopusID: 2-s2.0-33750366714ISBN: 3-540-46267-8OAI: diva2:445864
12th International Conference on Principles and Practice of Constraint Programming, CP 2006; Nantes; 25 September 2006 through 29 September 2006
QC 20111005Available from: 2011-10-05 Created: 2011-10-05 Last updated: 2011-10-05Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Schulte, Christian
By organisation
Electronic, Computer and Software Systems, ECS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 10 hits
ReferencesLink to record
Permanent link

Direct link