Generalized constraint propagation over the CLP scheme

Thierry Le Provost, Mark Wallace

Research output: Contribution to journalArticleResearchpeer-review

28 Citations (Scopus)

Abstract

Constraint logic programming is often described as logic programming with unification replaced by constraint solving over a computation domain. There is another, very different, CLP paradigm based on constraint satisfaction, where program-defined goals can be treated as constraints and handled using propagation. This paper proposes a generalization of propagation that enables it to be applied on arbitrary computation domains revealing that the two paradigms of CLP are orthogonal and can be freely combined. The main idea behind generalized propagation is to use whatever constraints are available over the computation domain to express restrictions on problem variables. Generalized propagation on a goal G requires that the system extracts a constraint approximating all the answers to G. This paper introduces a generic algorithm for generalized propagation called topological branch and bound, which avoids enumerating all the answers to G. Generalized propagation over the Herbrand universe has been implemented in a system called Propia, and we describe its behavior in some applications.

Original languageEnglish
Pages (from-to)319-359
Number of pages41
JournalThe Journal of Logic Programming
Volume16
Issue number3-4
DOIs
Publication statusPublished - 1 Jan 1993

Cite this