Solving linear diophantine constraints incrementally
Évelyne Contejean · 1993
In this paper, we show how to handle linear Diophantine constraints incrementally by using several variations of the algorithm by Contejean and Devie (hereafter called ABCD) for solving linear Diophantine systems [4, 5]. The basic algorithm is based on a certain enumeration of the potential solutions of a system, and termination is ensured by an adequate restriction on the search. This algorithm generalizes a previous algorithm due to Fortenbacher [2], which was restricted to the case of a single equation. Note that using Fortenbacher's algorithm for solving systems of Diophantine equations by repeatedly applying it to the successive equations is completely unrealistic: the tuple of variables in the solved equation must then be substituted in the rest of the system by a linear combination of the minimal solutions found in which the coefficients stand for new variables. Unfortunately, the number of these minimal solutions is actually exponential in both the number of variables and the v...