3530 articles – 5253 Notices  [english version]

inria-00069996, version 1

## Complete Solving of Linear Diophantine Equational and Inequational Systems without Adding Variables

Farid Ajili 1, Evelyne Contejean ()

N° RT-0175 (1995)

Résumé : In this report, we present an algorithm for solving {\em 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 \cite{contejean94ic} for solving linear Diophantine systems of equa­tions, which is itself a generalization of the algorithm of Fortenbacher \cite{clausen89} 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, {\em i.e.} provides a (finite) description of the set of solutions, it can be implemented with a {\em bounded} stack, and it admits an incremental version. All of these characteristics enable its easy integration in the CLP paradigm.

• 1 :  PROTHEO (INRIA Lorraine - LORIA)
• INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
• Domaine : Informatique/Autre
• Mots-clés : constraints – unification – solver – constraint logic programming – CLP – linear programming
• Référence interne : RT-0175

• inria-00069996, version 1
• oai:hal.inria.fr:inria-00069996
• Contributeur :
• Soumis le : Vendredi 19 Mai 2006, 18:46:46
• Dernière modification le : Mardi 20 Juin 2006, 13:58:27