|
[____]
This online help node and the nodes below it describe
the category of straight-line program groups (SLP-groups).
A straight-line program is formally a sequence [s1, s2, ..., sn]
such that each si is one of the following:
- (i)
- A generator of the SLP-group;
- (ii)
- A product sj sk, j<i, k<i;
- (iii)
- A power sjn, j<i;
- (iv)
- A conjugate sjsk, j<i, k<i.
Effectively, a straight-line program can be regarded
as a word in the generators which is stored as an expression
tree instead of a list of generator-exponent pairs.
The importance of such a category of groups is that storing a word as
an expression tree allows much faster evaluation of homomorphisms
given as the unique extension of a mapping of the generators into a
group of any category, as common subexpressions may be computed once
only, and powers or conjugates may be more efficiently computed in
the target group than by a linear product of generators and their
inverses.
The name in Magma for the category of SLP-groups is GrpSLP.
[Next][Prev] [Right] [____] [Up] [Index] [Root]
|