InforLorV4, PascalFrancis, Corpus, bibRecord, 000A97

On the complexity of counting the Hilbert basis of a linear Diophantine system

Identifieur interne : 000A97 ( PascalFrancis/Corpus ); précédent : 000A96; suivant : 000A98

On the complexity of counting the Hilbert basis of a linear Diophantine system

Auteurs : M. Hermann ; L. Juban ; P. G. Kolaitis

Source :

Lecture notes in computer science [ 0302-9743 ] ; 1999.

RBID : Pascal:99-0485948

Descripteurs français

Pascal (Inist)
- Intelligence artificielle, Programmation logique, Résolution système équation, Equation diophantienne, Problème Hilbert, Complexité calcul, Déduction automatique.

English descriptors

KwdEn :
- Artificial intelligence, Automatic deduction, Computational complexity, Diophantine equation, Equation system solving, Hilbert problem, Logical programming.

Abstract

We investigate the computational complexity of counting the Hilbert basis of a homogeneous system of linear Diophantine equations. We establish lower and upper bounds on the complexity of this problem by showing that counting the Hilbert basis is #P-hard and belongs to the class #NP. Moreover, we investigate the complexity of variants obtained by restricting the number of occurrences of the variables in the system.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0302-9743`
A05				`@2 1705`
A08	`01`	`1`	`ENG`	`@1 On the complexity of counting the Hilbert basis of a linear Diophantine system`
A09	`01`	`1`	`ENG`	`@1 LPAR '99 : logic for programming and automated reasoning : Tbilisi, 6-10 September 1999`
A11	`01`	`1`		`@1 HERMANN (M.)`
A11	`02`	`1`		`@1 JUBAN (L.)`
A11	`03`	`1`		`@1 KOLAITIS (P. G.)`
A12	`01`	`1`		`@1 GANZINGER (Harald) @9 ed.`
A12	`02`	`1`		`@1 MCALLESTER (David) @9 ed.`
A12	`03`	`1`		`@1 VORONKOV (Andrei) @9 ed.`
A14	`01`			`@1 LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239 @2 54506, Vandœuvre-lès-Nancy @3 FRA @Z 1 aut. @Z 2 aut.`
A14	`02`			`@1 Computer Science Department, University of California @2 Santa Cruz, CA 95064 @3 USA @Z 3 aut.`
A20				`@1 13-32`
A21				`@1 1999`
A23	`01`			`@0 ENG`
A26	`01`			`@0 3-540-66492-0`
A43	`01`			`@1 INIST @2 16343 @5 354000084578490020`
A44				`@0 0000 @1 © 1999 INIST-CNRS. All rights reserved.`
A45				`@0 1 p.3/4`
A47	`01`	`1`		`@0 99-0485948`
A60				`@1 P @2 C`
A61				`@0 A`
A64	`01`	`1`		`@0 Lecture notes in computer science`
A66	`01`			`@0 DEU`
C01	`01`		`ENG`	`@0 We investigate the computational complexity of counting the Hilbert basis of a homogeneous system of linear Diophantine equations. We establish lower and upper bounds on the complexity of this problem by showing that counting the Hilbert basis is #P-hard and belongs to the class #NP. Moreover, we investigate the complexity of variants obtained by restricting the number of occurrences of the variables in the system.`
C02	`01`	`X`		`@0 001D02C05`
C03	`01`	`X`	`FRE`	`@0 Intelligence artificielle @5 01`
C03	`01`	`X`	`ENG`	`@0 Artificial intelligence @5 01`
C03	`01`	`X`	`SPA`	`@0 Inteligencia artificial @5 01`
C03	`02`	`X`	`FRE`	`@0 Programmation logique @5 02`
C03	`02`	`X`	`ENG`	`@0 Logical programming @5 02`
C03	`02`	`X`	`SPA`	`@0 Programación lógica @5 02`
C03	`03`	`X`	`FRE`	`@0 Résolution système équation @5 03`
C03	`03`	`X`	`ENG`	`@0 Equation system solving @5 03`
C03	`03`	`X`	`SPA`	`@0 Resolución sistema ecuación @5 03`
C03	`04`	`X`	`FRE`	`@0 Equation diophantienne @5 04`
C03	`04`	`X`	`ENG`	`@0 Diophantine equation @5 04`
C03	`04`	`X`	`SPA`	`@0 Ecuación diofántica @5 04`
C03	`05`	`X`	`FRE`	`@0 Problème Hilbert @5 05`
C03	`05`	`X`	`ENG`	`@0 Hilbert problem @5 05`
C03	`05`	`X`	`SPA`	`@0 Problema Hilbert @5 05`
C03	`06`	`X`	`FRE`	`@0 Complexité calcul @5 06`
C03	`06`	`X`	`ENG`	`@0 Computational complexity @5 06`
C03	`06`	`X`	`SPA`	`@0 Complejidad computación @5 06`
C03	`07`	`X`	`FRE`	`@0 Déduction automatique @4 CD @5 96`
C03	`07`	`X`	`ENG`	`@0 Automatic deduction @4 CD @5 96`
N21				`@1 312`

A30	`01`	`1`	`ENG`	`@1 Logic for programming and automated reasoning. International conference @2 6 @3 Tbilisi GEO @4 1999-09-06`

Format Inist (serveur)

NO :	PASCAL 99-0485948 INIST
ET :	On the complexity of counting the Hilbert basis of a linear Diophantine system
AU :	HERMANN (M.); JUBAN (L.); KOLAITIS (P. G.); GANZINGER (Harald); MCALLESTER (David); VORONKOV (Andrei)
AF :	LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239/54506, Vandœuvre-lès-Nancy/France (1 aut., 2 aut.); Computer Science Department, University of California/Santa Cruz, CA 95064/Etats-Unis (3 aut.)
DT :	Publication en série; Congrès; Niveau analytique
SO :	Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 1999; Vol. 1705; Pp. 13-32; Bibl. 1 p.3/4
LA :	Anglais
EA :	We investigate the computational complexity of counting the Hilbert basis of a homogeneous system of linear Diophantine equations. We establish lower and upper bounds on the complexity of this problem by showing that counting the Hilbert basis is #P-hard and belongs to the class #NP. Moreover, we investigate the complexity of variants obtained by restricting the number of occurrences of the variables in the system.
CC :	001D02C05
FD :	Intelligence artificielle; Programmation logique; Résolution système équation; Equation diophantienne; Problème Hilbert; Complexité calcul; Déduction automatique
ED :	Artificial intelligence; Logical programming; Equation system solving; Diophantine equation; Hilbert problem; Computational complexity; Automatic deduction
SD :	Inteligencia artificial; Programación lógica; Resolución sistema ecuación; Ecuación diofántica; Problema Hilbert; Complejidad computación
LO :	INIST-16343.354000084578490020
ID :	99-0485948

Links to Exploration step

Pascal:99-0485948

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">On the complexity of counting the Hilbert basis of a linear Diophantine system</title>
<author><name sortKey="Hermann, M" sort="Hermann, M" uniqKey="Hermann M" first="M." last="Hermann">M. Hermann</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Juban, L" sort="Juban, L" uniqKey="Juban L" first="L." last="Juban">L. Juban</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Kolaitis, P G" sort="Kolaitis, P G" uniqKey="Kolaitis P" first="P. G." last="Kolaitis">P. G. Kolaitis</name>
<affiliation><inist:fA14 i1="02"><s1>Computer Science Department, University of California</s1>
<s2>Santa Cruz, CA 95064</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">99-0485948</idno>
<date when="1999">1999</date>
<idno type="stanalyst">PASCAL 99-0485948 INIST</idno>
<idno type="RBID">Pascal:99-0485948</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A97</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">On the complexity of counting the Hilbert basis of a linear Diophantine system</title>
<author><name sortKey="Hermann, M" sort="Hermann, M" uniqKey="Hermann M" first="M." last="Hermann">M. Hermann</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Juban, L" sort="Juban, L" uniqKey="Juban L" first="L." last="Juban">L. Juban</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Kolaitis, P G" sort="Kolaitis, P G" uniqKey="Kolaitis P" first="P. G." last="Kolaitis">P. G. Kolaitis</name>
<affiliation><inist:fA14 i1="02"><s1>Computer Science Department, University of California</s1>
<s2>Santa Cruz, CA 95064</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="1999">1999</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Artificial intelligence</term>
<term>Automatic deduction</term>
<term>Computational complexity</term>
<term>Diophantine equation</term>
<term>Equation system solving</term>
<term>Hilbert problem</term>
<term>Logical programming</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Intelligence artificielle</term>
<term>Programmation logique</term>
<term>Résolution système équation</term>
<term>Equation diophantienne</term>
<term>Problème Hilbert</term>
<term>Complexité calcul</term>
<term>Déduction automatique</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We investigate the computational complexity of counting the Hilbert basis of a homogeneous system of linear Diophantine equations. We establish lower and upper bounds on the complexity of this problem by showing that counting the Hilbert basis is #P-hard and belongs to the class #NP. Moreover, we investigate the complexity of variants obtained by restricting the number of occurrences of the variables in the system.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01>
<fA05><s2>1705</s2>
</fA05>
<fA08 i1="01" i2="1" l="ENG"><s1>On the complexity of counting the Hilbert basis of a linear Diophantine system</s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG"><s1>LPAR '99 : logic for programming and automated reasoning : Tbilisi, 6-10 September 1999</s1>
</fA09>
<fA11 i1="01" i2="1"><s1>HERMANN (M.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>JUBAN (L.)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>KOLAITIS (P. G.)</s1>
</fA11>
<fA12 i1="01" i2="1"><s1>GANZINGER (Harald)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="02" i2="1"><s1>MCALLESTER (David)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="03" i2="1"><s1>VORONKOV (Andrei)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>Computer Science Department, University of California</s1>
<s2>Santa Cruz, CA 95064</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</fA14>
<fA20><s1>13-32</s1>
</fA20>
<fA21><s1>1999</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA26 i1="01"><s0>3-540-66492-0</s0>
</fA26>
<fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000084578490020</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 1999 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>1 p.3/4</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>99-0485948</s0>
</fA47>
<fA60><s1>P</s1>
<s2>C</s2>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64>
<fA66 i1="01"><s0>DEU</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>We investigate the computational complexity of counting the Hilbert basis of a homogeneous system of linear Diophantine equations. We establish lower and upper bounds on the complexity of this problem by showing that counting the Hilbert basis is #P-hard and belongs to the class #NP. Moreover, we investigate the complexity of variants obtained by restricting the number of occurrences of the variables in the system.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02C05</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Intelligence artificielle</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Artificial intelligence</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Inteligencia artificial</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Programmation logique</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Logical programming</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Programación lógica</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Résolution système équation</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Equation system solving</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Resolución sistema ecuación</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>Problème Hilbert</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Hilbert problem</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Problema Hilbert</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Complexité calcul</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Computational complexity</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Complejidad computación</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Déduction automatique</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Automatic deduction</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fN21><s1>312</s1>
</fN21>
</pA>
<pR><fA30 i1="01" i2="1" l="ENG"><s1>Logic for programming and automated reasoning. International conference</s1>
<s2>6</s2>
<s3>Tbilisi GEO</s3>
<s4>1999-09-06</s4>
</fA30>
</pR>
</standard>
<server><NO>PASCAL 99-0485948 INIST</NO>
<ET>On the complexity of counting the Hilbert basis of a linear Diophantine system</ET>
<AU>HERMANN (M.); JUBAN (L.); KOLAITIS (P. G.); GANZINGER (Harald); MCALLESTER (David); VORONKOV (Andrei)</AU>
<AF>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239/54506, Vandœuvre-lès-Nancy/France (1 aut., 2 aut.); Computer Science Department, University of California/Santa Cruz, CA 95064/Etats-Unis (3 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 1999; Vol. 1705; Pp. 13-32; Bibl. 1 p.3/4</SO>
<LA>Anglais</LA>
<EA>We investigate the computational complexity of counting the Hilbert basis of a homogeneous system of linear Diophantine equations. We establish lower and upper bounds on the complexity of this problem by showing that counting the Hilbert basis is #P-hard and belongs to the class #NP. Moreover, we investigate the complexity of variants obtained by restricting the number of occurrences of the variables in the system.</EA>
<CC>001D02C05</CC>
<FD>Intelligence artificielle; Programmation logique; Résolution système équation; Equation diophantienne; Problème Hilbert; Complexité calcul; Déduction automatique</FD>
<ED>Artificial intelligence; Logical programming; Equation system solving; Diophantine equation; Hilbert problem; Computational complexity; Automatic deduction</ED>
<SD>Inteligencia artificial; Programación lógica; Resolución sistema ecuación; Ecuación diofántica; Problema Hilbert; Complejidad computación</SD>
<LO>INIST-16343.354000084578490020</LO>
<ID>99-0485948</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A97 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000A97 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:99-0485948
   |texte=   On the complexity of counting the Hilbert basis of a linear Diophantine system
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

On the complexity of counting the Hilbert basis of a linear Diophantine system

On the complexity of counting the Hilbert basis of a linear Diophantine system

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri