Intuition behind straight-line programs Wikipedia defines straight-line programs in the following manner:


  In mathematics, more specifically in computational algebra[disambiguation needed], a straight-line program (SLP) for a finite group G = 〈S〉 is a finite sequence L of elements of G such that every element of L that belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses.


This is a fairly confusing definition to unpack. However, in some meaningful sense, I believe the main idea here is that there are no comparisons allowed. Since there are no comparisons, the "computation tree" ends up being a straight line - hence the name "straight-line program."

In modern terms, is this the correct idea? Or are there even more subtle restrictions than this on what sorts of programs are allowed to be straight-line programs?
A straight-line program is one with no branches, no loops, no conditional statements, no comparisons -- just a sequence of basic operations.

A straight-line program for a finite group $G$ is a straight-line program in a very simple language with an unlimited number of registers $r_1,r_2,r_3,\dots$ and with only two legal operations:


$r_i := \text{inverse}(r_j)$ 
$r_i := \text{multiply}(r_j,r_k)$


You specify $i,j,k$ for each line of the program; those are constants.  Each register holds a group element.  



For instance, the following is a straight-line program that computes the cube of the element in $r_1$ and stores the result in $r_3$:


$r_2 := \text{multiply}(r_1, r_1)$
$r_3 := \text{multiply}(r_1, r_2)$


Here is another program that computes the same thing, but in a different way:


$r_2 := \text{multiply}(r_1, r_1)$
$r_4 := \text{multiply}(r_2, r_2)$
$r_5 := \text{inverse}(r_1)$
$r_3 := \text{multiply}(r_4, r_5)$