Generalized constraint propagation over the CLP scheme

AbstractConstraint 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