Groups with Elements given as Straight-Line Programs

This is a class of finitely generated free groups whose elements are represented as ``straight-line'' programs and which are referred to as SLP-groups for brevity. Typically a SLP-group is used when it is necessary to evaluate long words in a permutation or matrix group G. If G is defined on d generators then a d-generator SLP-group F is defined together with the homomorphism of F onto G which sends the i-th generator of F to the i-th generator of G. Words corresponding to elements of G are built as elements of Fwhere they are represented as expression trees thereby allowing very fast evaluation of long words in G.

• Construction
• Arithmetic with straight-line programs
• Homomorphism from a blackbox group onto an arbitrary group
• Random generation of elements (Cellar, Leedham-Green, Murray, Niemeyer, O'Brien algorithm)