• Up
• Contents
• Index
• Search
• Next »

Introduction

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 [s₁, s₂, ..., s_n] such that each s_i is one of the following:

(i)

A generator of the SLP-group;

(ii)

A product s_j s_k, j<i, k<i;

(iii)

A power s_jⁿ, j<i;

(iv)

A conjugate s_j^s_k, 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.

• Up
• Contents
• Index
• Search
• Next »