Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Complete Solving of Linear Diophantine Equations and
Inequations without Adding Variables
Complete Solving of Linear Diophantine Equations and
Inequations without Adding Variables
Farid Ajili and Evelyne Contejean
In this paper, we present an algorithm for solving directly
linear Diophantine systems of both equations and inequations. Here
directly means without adding slack variables for encoding
inequalities as equalities. This algorithm is an extension of the
algorithm due to Contejean and Devie for solving
linear Diophantine systems of equations, which is itself a
generalization of the algorithm of Fortenbacher 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.