Discrete Mathematics & Theoretical Computer Science, Vol 1 (1997)

Font Size:  Small  Medium  Large
DMTCS vol 1 no 1 (1997), pp. 1-16

Discrete Mathematics & Theoretical Computer Science


Volume 1 n° 1 (1997), pp. 1-16

author:Csaba Schneider
title:Computing nilpotent quotients in finitely presented Lie rings
keywords:Lie rings nilpotent Lie rings finitely presented Lie rings nilpotent presentation
abstract:A nilpotent quotient algorithm for finitely presented Lie rings over Z (and Q) 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.
reference: Csaba Schneider (1997), Computing nilpotent quotients in finitely presented Lie rings, Discrete Mathematics and Theoretical Computer Science 1, pp. 1-16
ps-source:dm010101.ps (390 K)
pdf-source:dm010101.pdf (191 K)

The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Automatically produced on Tue Jan 19 17:48:59 MET 1999 by gustedt