Tech Report CS-90-24

The Cardinality Operator: A New Logical Connective for Constraint Logic Programming

Pascal Van Hentenryck and Yves Deville

October 1990

Abstract:

This paper is an attempt to increase the (operational) expressiveness and efficiency of constraint logic programming (CLP). We propose a programming abstraction, the cardinality operator, that gives CLP users a new way of combining (primitive) constraints to build non-primitive ones. Declaratively, the cardinality operator is a new logical connective. Operationally, it implements a principle well-known in artificial intelligence and operations research, {\em ``Infer simple constraints from difficult ones'',} and is based on constraint-solving, constraint-entailment, and simple arithmetic reasoning. The cardinality operator is independent of the computation model, subsumes a number of control mechanisms and constraints that were sometimes introduced in a rather ad-hoc manner, and can be seen as a new relational combinator in the {\em ask \& tell} framework. Programming examples and computation results are given that show the versatility and efficiency of the operator.

(complete text in pdf)