Sub-groups of Zn, standard basis, and linear diophantine systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1991

Sub-groups of Zn, standard basis, and linear diophantine systems

Résumé

We caracterize a (affine) sub-group of Zn by a polynomial ideal and standard (Gröbner) basis. We show how to use these standard basis to solve directly many algorithmic problems on (affine) sub-groups and their non-negative parts : * the membership problem * the triviality problem * find the smallest non zero vector * find the minimal non-negative elements * solve linear diohantine systems (Ax = 0, x>=0), (Ax = b, x>=0), Ax <= b on integers, and find smallest solutions Finally we conjecture other properties of these standard basis

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1510.pdf (411.69 Ko) Télécharger le fichier

Dates et versions

inria-00075052 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00075052 , version 1

Citer

Loïc Pottier. Sub-groups of Zn, standard basis, and linear diophantine systems. [Research Report] RR-1510, INRIA. 1991, pp.11. ⟨inria-00075052⟩
43 Consultations
24 Téléchargements

Partager

Gmail Facebook X LinkedIn More