zbMATH — the first resource for mathematics

Towards “propagation = logic + control”. (English) Zbl 1131.68368
Etalle, Sandro (ed.) et al., Logic programming. 22nd international conference, ICLP 2006, Seattle, WA, USA, August 17–20, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-36635-5/pbk). Lecture Notes in Computer Science 4079, 102-116 (2006).
Summary: Constraint propagation algorithms implement logical inference. For efficiency, it is essential to control whether and in what order basic inference steps are taken. We provide a high-level framework that clearly differentiates between information needed for controlling propagation versus that needed for the logical semantics of complex constraints composed from primitive ones. We argue for the appropriateness of our controlled propagation framework by showing that it captures the underlying principles of manually designed propagation algorithms, such as literal watching for unit clause propagation and the lexicographic ordering constraint. We provide an implementation and benchmark results that demonstrate the practicality and efficiency of our framework.
For the entire collection see [Zbl 1130.68008].

68N17 Logic programming
Full Text: DOI