© 1993 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Variable Elimination for Disequations in Generalized Linear Constraint Systems
G.I.A. Faculté des Sciences de Luminy, 163 Avenue de Luminy, cas 901, F-13288 Marseille cedex 9, France
This paper is concerned with the case of generalized linear constraint systems. A generalized linear constraints systems is the conjunction of a sub-system of equations E, a sub-system of inequations I (
), an a sub-system of disequations D (
). We first of all establish that the variable elimination operation on a generalized linear constraint system E, I, D has, as its result, a generalized linear constraint system E', I', D'. We then show that E', I' does not depend on D, and that the disequations of D are independent from one another for the variable elimination operation. Next, we present two algorithms for variable elimination in the disequation sub-system D. The first algorithm can be easily integrated into an algorithm dealing with variable elimination in inequation systems by the Fourier elimination method. The variables are eliminated one after another. The second algorithm assumes that the projection E', I' is known. It is based on new properties that we establish. It globally eliminates the variables in one single operation. The numerous independencies allow for a high degree of parallelism which we take advantage of.*
Received January 1993. revised May 1993.
* G.I.A. Faculté des Sciences de Luminy, 163 Avenue de Luminy, cas 901, F-13288 Marseille cedex 9, France