Avoiding slack variables in the solving of linear diophantine equations and inequations
Identifieur interne : 000C13 ( PascalFrancis/Curation ); précédent : 000C12; suivant : 000C14Avoiding 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.
pA |
|
---|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000C66
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="1"><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>
</affiliation>
</author>
<author><name sortKey="Contejean, E" sort="Contejean, E" uniqKey="Contejean E" first="E." last="Contejean">E. Contejean</name>
<affiliation wicri:level="1"><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>
</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>
</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="1"><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>
</affiliation>
</author>
<author><name sortKey="Contejean, E" sort="Contejean, E" uniqKey="Contejean E" first="E." last="Contejean">E. Contejean</name>
<affiliation wicri:level="1"><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>
</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>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0304-3975</s0>
</fA01>
<fA02 i1="01"><s0>TCSCDI</s0>
</fA02>
<fA03 i2="1"><s0>Theor. comput. sci.</s0>
</fA03>
<fA05><s2>173</s2>
</fA05>
<fA06><s2>1</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>Avoiding slack variables in the solving of linear diophantine equations and inequations</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>AJILI (F.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>CONTEJEAN (E.)</s1>
</fA11>
<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>
</fA14>
<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>
</fA14>
<fA20><s1>183-208</s1>
</fA20>
<fA21><s1>1997</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA24 i1="01"><s0>eng</s0>
</fA24>
<fA43 i1="01"><s1>INIST</s1>
<s2>17243</s2>
<s5>354000063259310014</s5>
</fA43>
<fA44><s0>9000</s0>
<s1>© 1997 Elsevier Science B.V. All rights reserved.</s1>
</fA44>
<fA47 i1="01" i2="1"><s0>97-0270951</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Theoretical computer science</s0>
</fA64>
<fA66 i1="01"><s0>NLD</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>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.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Système inéquation</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Inequation system</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Sistema inecuación</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Système équation</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Equation system</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Sistema ecuación</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Système linéaire</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Linear system</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Sistema lineal</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Equation diophantienne</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Diophantine equation</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Ecuación diofántica</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Algorithme</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Algorithm</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="GER"><s0>Algorithmus</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Algoritmo</s0>
<s5>05</s5>
</fC03>
<fN21><s1>153</s1>
</fN21>
</pA>
</standard>
</inist>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C13 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000C13 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= PascalFrancis |étape= Curation |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. | ![]() |