2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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)$
Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks, makes sense. So for some RAM with whatever instruction set, an algorithm for on that RAM is an SLP iff it halts and has no comparisons/branching. Right? $\endgroup$
    – Mike Battaglia
    Jun 2, 2017 at 23:55
  • $\begingroup$ @MikeBattaglia, no. These programs (SLPs for groups) have only registers -- no memory, no pointers, no arrays, no indirect addressing, etc. $\endgroup$
    – D.W. ♦
    Jun 2, 2017 at 23:56
  • $\begingroup$ How are you distinguishing between "registers" and "memory" here? For most RAM models I've studied, the only "memory" I've seen is the set of registers. But if the additional restriction here is that indirection is also not allowed, that makes sense. $\endgroup$
    – Mike Battaglia
    Jun 3, 2017 at 0:05
  • $\begingroup$ @MikeBattaglia, memory lets you do something like $r_2 = \text{load}(r_1)$, i.e., read from an address specified by the value in register $r_1$. This model doesn't let you do that. All register indices must be compile-time constants -- you can't have something like $r_{r_2}$. In other words, no array lookups, no table lookups, no pointers, no indirection. $\endgroup$
    – D.W. ♦
    Jun 3, 2017 at 3:05
  • $\begingroup$ Thanks, that is interesting. I'm wondering, what is the central idea behind these restrictions? I guess the idea is that you can effectively "simulate" a comparison with indirection, so if you're banning the former you might as well ban the latter, right? $\endgroup$
    – Mike Battaglia
    Jun 5, 2017 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.