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

Loïc Pottier 1
1 SAFIR - Algebraic Formal Systems for Industry and Research
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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
Type de document :
Rapport
[Research Report] RR-1510, INRIA. 1991, pp.11
Liste complète des métadonnées

https://hal.inria.fr/inria-00075052
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 17:20:21
Dernière modification le : samedi 27 janvier 2018 - 01:31:04
Document(s) archivé(s) le : mardi 12 avril 2011 - 20:49:53

Fichiers

Identifiants

  • HAL Id : inria-00075052, version 1

Collections

Citation

Loïc Pottier. Sub-groups of Zn, standard basis, and linear diophantine systems. [Research Report] RR-1510, INRIA. 1991, pp.11. 〈inria-00075052〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

55