Towards “Propagation = Logic + Control”

DOI10.1007/11799573_10zbMATH Open1131.68368arXivcs/0608015OpenAlexW1551372652MaRDI QIDQ5449595FDOQ5449595

Authors: Sebastian Brand, Roland H. C. Yap 

Publication date: 11 March 2008

Published in: Logic Programming (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/cs/0608015

Recommendations

• Constraint propagation for first-order logic and inductive definitions
• scientific article; zbMATH DE number 1234564
• The essence of constraint propagation
• scientific article; zbMATH DE number 1487973
• scientific article; zbMATH DE number 370484

Mathematics Subject Classification ID

Logic programming (68N17)

Cited In (3)

• Constraint propagation for first-order logic and inductive definitions
• Fast and Flexible Difference Constraint Propagation for DPLL(T)
• Implementing logical connectives in constraint programming

This page was built for publication: Towards “Propagation = Logic + Control”

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5449595)