Tech Report CS-90-24

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

Pascal Van Hentenryck and Yves Deville

October 1990


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)