Avoiding slack variables in the solving of linear diophantine equations and inequations
Identifieur interne : 00C538 ( Main/Merge ); précédent : 00C537; suivant : 00C539Avoiding slack variables in the solving of linear diophantine equations and inequations
Auteurs : F. Ajili [France] ; E. Contejean [France]Source :
- Theoretical computer science [ 0304-3975 ] ; 1997.
Descripteurs français
- Pascal (Inist)
English descriptors
Abstract
Copyright (c) 1996 Elsevier Science B.V. All rights reserved. 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 (1994) for solving linear Diophantine systems of equations, which is itself a generalization of the algorithm of Fortenbacher (Clausen and Fortenbacher, 1989) 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.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000C66
- to stream PascalFrancis, to step Curation: 000C13
- to stream PascalFrancis, to step Checkpoint: 000C41
Links to Exploration step
Pascal:97-0270951Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Avoiding slack variables in the solving of linear diophantine equations and inequations</title><author><name sortKey="Ajili, F" sort="Ajili, F" uniqKey="Ajili F" first="F." last="Ajili">F. Ajili</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>INRIA Lorraine & CRIN, 615 rue du jardin botanique BP 101</s1><s2>54602 Villers-lès-Nancy Cedex</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Villers-lès-Nancy</settlement></placeName></affiliation></author><author><name sortKey="Contejean, E" sort="Contejean, E" uniqKey="Contejean E" first="E." last="Contejean">E. Contejean</name><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>LRI, CNRS URA 410, Bât 490, Université Paris-Sud, Centre d’Orsay</s1><s2>91405 Orsay Cedex</s2><s3>FRA</s3><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Orsay</settlement></placeName><orgName type="university">Université Paris-Sud</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">97-0270951</idno><date when="1997">1997</date><idno type="stanalyst">PASCAL 97-0270951 Elsevier</idno><idno type="RBID">Pascal:97-0270951</idno><idno type="wicri:Area/PascalFrancis/Corpus">000C66</idno><idno type="wicri:Area/PascalFrancis/Curation">000C13</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000C41</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C41</idno><idno type="wicri:doubleKey">0304-3975:1997:Ajili F:avoiding:slack:variables</idno><idno type="wicri:Area/Main/Merge">00C538</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Avoiding slack variables in the solving of linear diophantine equations and inequations</title><author><name sortKey="Ajili, F" sort="Ajili, F" uniqKey="Ajili F" first="F." last="Ajili">F. Ajili</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>INRIA Lorraine & CRIN, 615 rue du jardin botanique BP 101</s1><s2>54602 Villers-lès-Nancy Cedex</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Villers-lès-Nancy</settlement></placeName></affiliation></author><author><name sortKey="Contejean, E" sort="Contejean, E" uniqKey="Contejean E" first="E." last="Contejean">E. Contejean</name><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>LRI, CNRS URA 410, Bât 490, Université Paris-Sud, Centre d’Orsay</s1><s2>91405 Orsay Cedex</s2><s3>FRA</s3><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Orsay</settlement></placeName><orgName type="university">Université Paris-Sud</orgName></affiliation></author></analytic><series><title level="j" type="main">Theoretical computer science</title><title level="j" type="abbreviated">Theor. comput. sci.</title><idno type="ISSN">0304-3975</idno><imprint><date when="1997">1997</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Theoretical computer science</title><title level="j" type="abbreviated">Theor. comput. sci.</title><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Diophantine equation</term><term>Equation system</term><term>Inequation system</term><term>Linear system</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Système inéquation</term><term>Système équation</term><term>Système linéaire</term><term>Equation diophantienne</term><term>Algorithme</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Copyright (c) 1996 Elsevier Science B.V. All rights reserved. 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 (1994) for solving linear Diophantine systems of equations, which is itself a generalization of the algorithm of Fortenbacher (Clausen and Fortenbacher, 1989) 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.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Île-de-France</li></region><settlement><li>Orsay</li><li>Villers-lès-Nancy</li></settlement><orgName><li>Université Paris-Sud</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Ajili, F" sort="Ajili, F" uniqKey="Ajili F" first="F." last="Ajili">F. Ajili</name></region><name sortKey="Contejean, E" sort="Contejean, E" uniqKey="Contejean E" first="E." last="Contejean">E. Contejean</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00C538 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00C538 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= Pascal:97-0270951
|texte= Avoiding slack variables in the solving of linear diophantine equations and inequations
}}
| This area was generated with Dilib version V0.6.33. |  |