About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Symbolic Computation
Paper
A canonical form for generalized linear constraints
Abstract
The integration of the constraint solving paradigm in programming languages raises a number of new issues. Foremost is the need for a useful canonical form for the representation of constraints. In the context of an extended class of linear arithmetic constraints we develop a natural canonical representation and we design polynomial time algorithms for deciding solvability and generating the canonical form. Important issues encountered include negative constraints, the elimination of redundancy and parallelism. The canonical form allows us to decide by means of a simple syntactic check the equivalence of two sets of constraints and provides the starting point for a symbolic computation system. It has, moreover, other applications and we show in particular that it yields a completeness theorem for constraint propagation and is an appropriate tool to be used in connection with constraint based programming languages. © 1992.