Computing nilpotent quotients in finitely presented Lie rings

Abstract : A nilpotent quotient algorithm for finitely presented Lie rings over \textbfZ (and \textbfQ) is described. The paper studies the graded and non-graded cases separately. The algorithm computes the so-called nilpotent presentation for a finitely presented, nilpotent Lie ring. A nilpotent presentation consists of generators for the abelian group and the products expressed as linear combinations for pairs formed by generators. Using that presentation the word problem is decidable in L. Provided that the Lie ring L is graded, it is possible to determine the canonical presentation for a lower central factor of L. Complexity is studied and it is shown that optimising the presentation is NP-hard. Computational details are provided with examples, timing and some structure theorems obtained from computations. Implementation in C and GAP interface are available.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 1997, 1, pp.1-16
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00955687
Contributeur : Alain Monteil <>
Soumis le : mercredi 5 mars 2014 - 09:30:26
Dernière modification le : mercredi 29 novembre 2017 - 10:26:24
Document(s) archivé(s) le : jeudi 5 juin 2014 - 10:51:46

Fichier

dm010101.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00955687, version 1

Collections

Citation

Csaba Schneider. Computing nilpotent quotients in finitely presented Lie rings. Discrete Mathematics and Theoretical Computer Science, DMTCS, 1997, 1, pp.1-16. 〈hal-00955687〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

159