Comptage de l'ensemble des éléments de la base de Hilbert d'un système d'équations diophantiennes linéaires

Laurent Juban 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : La résolution en nombre entiers positifs des équations linéaires à coefficients entiers encore connues sous le nom d'équations diophantiennes linéaires, joue un rôle fondamental dans l'unification modulo AC. En effet, tous les algorithmes généraux d'unification modulo AC connus à ce jour font appel implicitement ou explicitement à ce type d'équation. Le problème de comptage de l'ensemble minimal et complet des solutions d'un système d'équations diophantiennes linéaires appartient dans le cas général à la classe $\#NP$. Nous avons étudié des sous-problèmes en restreignant le nombre d'équations et la multiplicité de chaque variable. Nous avons montré, entre autre, qu'il y a trois cas intéressants à étudier : le cas où la multiplicité de chaque variable est au plus trois qui appartient à la classe $\#NP$, le cas où la multiplicité de chaque variable est au plus deux qui appartient à la classe $\#P$ et le cas le plus simple où chaque variable du système est de multiplicité un qui est polynômial. De plus, nous avons pu montrer que pour toute solution minimale d'un système d'équations diophantiennes linéaires où chaque variable est au plus de multiplicité deux, chaque variable prendra au plus la valeur deux dans toutesolution minimale.
Type de document :
Rapport
[Interne] 98-R-066 || juban98a, 1998, 31 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00098731
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:21:26
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 11:44:55

Fichiers

Identifiants

  • HAL Id : inria-00098731, version 1

Collections

Citation

Laurent Juban. Comptage de l'ensemble des éléments de la base de Hilbert d'un système d'équations diophantiennes linéaires. [Interne] 98-R-066 || juban98a, 1998, 31 p. 〈inria-00098731〉

Partager

Métriques

Consultations de la notice

151

Téléchargements de fichiers

33