zbMATH — the first resource for mathematics

Avoiding slack variables in the solving of linear diophantine equations and inequations. (English) Zbl 0903.11033
Summary: The authors present an algorithm for solving directly linear diophantine systems of both equations and inequalities. Here directly means without adding slack variables for encoding inequalities as equalities. This algorithm is an extension of the algorithm due to E. Contejean and H. Devie [Inf. Comput. 113, 143-172 (1994; Zbl 0809.11015)] for solving linear diophantine systems of equations, which is itself a generalization of the algorithm of Fortenbacher [M. Clausen and A. Fortenbacher, J. Symb. Comput. 8, No. 1/2, 201-216 (1989; Zbl 0674.10011)] for solving a single linear diophantine equation. All the nice properties of the algorithm of Contejean and Devie are still satisfied by the new algorithm: it is complete, i.e. provides a (finite) description of the set of solutions, it can be implemented with a bounded stack, and it admits an incremental version. All of these characteristics enable its easy integration in the CLP paradigm.

MSC:
 11Y50 Computer solution of Diophantine equations 11D04 Linear Diophantine equations 68W30 Symbolic computation and algebraic computation 11D75 Diophantine inequalities 68N17 Logic programming 90C05 Linear programming
Full Text:
References:
 [1] Abdulrab, H.; Maksimenko, M., General solutions of systems of linear Diophantine equations and inequations, () [2] Ajili, F., Etude de la résolution de contraintes diophantiennes linéaires sur LES entiers naturels, () [3] Ajili, F.; Contejean, E., Complete solving of linear and Diophantine equational and inequational systems without adding variables, () [4] Ajili, F.; Contejean, E.; Domenjoud, E.; Filgueiras, M.; Kirchner, C.; Tomás, A.-P., Solving linear Diophantine equations: the state of the art, (1995), in preparation [5] Boudet, A.; Contejean, Evelyne; Devie, Hervé, A new AC-unification algorithm with a new algorithm for solving Diophantine equations, (), 289-299 [6] Chou, T.J.; Collins, G.E., Algorithms for the solution of systems of linear Diophantine equations, SIAM J. comput., 11, 687-708, (1982) · Zbl 0498.65022 [7] Clausen, M.; Fortenbacher, A., Efficient solution of linear Diophantine equations, J. symbolic comput., 8, 201-216, (1989) · Zbl 0674.10011 [8] Clifford, A.H.; Preston, G.B., The algebraic theory of semigroups, (), There are two volumes. The second was published in 1967 · Zbl 0178.01203 [9] Contejean, E., Solving ∗-problems modulo distributivity by a reduction to AC1-unification, J. symbolic comput., 16, 493-521, (1993) · Zbl 0803.68059 [10] Contejean, E.; Devie, H., An efficient algorithm for solving systems of Diophantine equations, Inform. comput., 113, 1, 143-172, (1994) · Zbl 0809.11015 [11] Domenjoud, E., Outils pour la déduction automatique dans LES théories associatives-commutatives, Thèse de doctorat de l’université de Nancy I, (1991) [12] Domenjoud, E., Solving systems of linear Diophantine equations: an algebraic approach, () · Zbl 0782.11008 [13] Domenjoud, E.; Tomás, A.P., From elliot-mac mahon to an algorithm for general linear constraints on naturals, () [14] Filgueiras, M.; Tomás, A.P., Fast methods for solving linear Diophantine equations, (), 297-306 [15] Guckenbiehl, T.; Herold, A., Solving linear Diophantine equations, Tech. report SEKI-85-IV-KL, (1985) [16] Herold, A.; Siekmann, J.H., Unification in abelian semi-groups, J. automat. reason., 3, 247-283, (1987) · Zbl 0637.68106 [17] Huet, G., An algorithm to generate the basis of solutions to homogeneous linear Diophantine equations, Inform. process. lett., 7, 3, (1978) · Zbl 0377.10011 [18] Karmarkar, N.; Karmarkar, N., A new polynomial algorithm for linear programming, (), Combinatorica, 4, 373-395, (1984), revised version: · Zbl 0557.90065 [19] Khachiyan, L.G., Polynomial algorithms in linear programming, Zh. vychisl. mat. i matematicheskoi fiziki, 20, 51-68, (1980) · Zbl 0431.90043 [20] Kirchner, C., From unification in combination of equational theories to a new AC unification algorithm, (), 171-210 [21] Lambert, J.L.; Lambert, J.L., Une borne pour LES générateurs des solutions entières positives d’une équation diophantienne linéaire, comptes rendus de l’académie des sciences de Paris, serie I, comptes rendus de l’académie des sciences de Paris, serie I, 305, 40, (1987) · Zbl 0615.10022 [22] Makanin, G.S., Algorithmic decidability of the rank of constant free equations in a free semigroup, Dokl. akad. nauk. SSSR, 243, 243, (1978) · Zbl 0417.20050 [23] Pottier, L., Minimal solutions of linear Diophantine systems: bounds and algorithms, (), 162-173 [24] Romeuf, J.F., A polynomial algorithm for solving systems of two linear Diophantine equations, () [25] Schrijver, A., Theory of linear and integer programming, (1986), Wiley New York · Zbl 0665.90063 [26] Sogno, J.C., Analysis of standard and new algorithms for the integer and linear constraint satisfaction problem, () [27] Stickel, M., A unification algorithm for associative-commutative functions, J. ACM, 28, 423-434, (1981) · Zbl 0462.68075 [28] Van Hentenryck, P., Constraint satisfaction in logic programming, (1989), MIT Press Cambridge, MA [29] Van Hentenryck, P.; Simonis, H.; Dincbas, M., Constraint satisfaction using constraint logic programming, Artificial intelligence, 58, 1-3, 113-159, (1992) · Zbl 0782.68028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.