Change search
ReferencesLink to record
Permanent link

Direct link
Weakly Monotonic Propagators
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).ORCID iD: 0000-0002-6283-7004
2009 (English)In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING / [ed] Gent IP, 2009, Vol. 5732, 723-730 p.Conference paper (Refereed)
Abstract [en]

Today's models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. These models do not comply with reality: today's constraint, programming systems actually use non-monotonic propagators. This paper introduces the first realistic model of constraint propagation by assuming it propagator to be weakly monotonic (complying with the constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. The important insight is that weak monotonicity makes propagation in combination. with search well behaved. A case study suggests that non-monotonicity call be seen as all opportunity for more efficient propagation.

Place, publisher, year, edition, pages
2009. Vol. 5732, 723-730 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 5732
Keyword [en]
Constraint programming systems, Constraint propagation, Constraint solvers, Minimal properties, Monotonicity, Non-monotonicity, Realistic model, Computer programming
National Category
Computer Science
URN: urn:nbn:se:kth:diva-30347DOI: 10.1007/978-3-642-04244-7_56ISI: 000273241200053ScopusID: 2-s2.0-70350413800ISBN: 978-3-642-04243-0OAI: diva2:401707
15th International Conference on Principles and Practice of Constraint Programming (CP 2009), Lisbon, PORTUGAL, SEP 20-24, 2009

QC 20110303

Available from: 2011-03-03 Created: 2011-02-24 Last updated: 2016-05-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schulte, Christian
By organisation
Software and Computer Systems, SCS (Closed 20120101)
Computer 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

Altmetric score

Total: 10 hits
ReferencesLink to record
Permanent link

Direct link