Generalized constraint propagation over the CLP scheme

Thierry Le Provost, Mark Wallace

Research output: Contribution to journalArticleResearchpeer-review

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

Le Provost, Thierry ; Wallace, Mark. / Generalized constraint propagation over the CLP scheme. In: The Journal of Logic Programming. 1993 ; Vol. 16, No. 3-4. pp. 319-359.
@article{7bdc7850e41d49539abcf53bc5b7f376,
title = "Generalized constraint propagation over the CLP scheme",
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.",
author = "{Le Provost}, Thierry and Mark Wallace",
year = "1993",
month = "1",
day = "1",
doi = "10.1016/0743-1066(93)90047-K",
language = "English",
volume = "16",
pages = "319--359",
journal = "Journal of Logic Programming",
issn = "0743-1066",
number = "3-4",

}

Generalized constraint propagation over the CLP scheme. / Le Provost, Thierry; Wallace, Mark.

In: The Journal of Logic Programming, Vol. 16, No. 3-4, 01.01.1993, p. 319-359.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Generalized constraint propagation over the CLP scheme

AU - Le Provost, Thierry

AU - Wallace, Mark

PY - 1993/1/1

Y1 - 1993/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027624139&partnerID=8YFLogxK

U2 - 10.1016/0743-1066(93)90047-K

DO - 10.1016/0743-1066(93)90047-K

M3 - Article

VL - 16

SP - 319

EP - 359

JO - Journal of Logic Programming

JF - Journal of Logic Programming

SN - 0743-1066

IS - 3-4

ER -