**Authors:** Richard Beigel and Howard Straubing

**Abstract:**
Identify a string *x* over {0,1} with the positive integer whose
binary representation is 1*x*. We say that a self-reduction is
*k*-local if on input *x* all queries belong to
{*x* - 1*x* - *k**k*-locally
self-reducible sets belong to PSPACE. However, the power of
*k*-local self-reductions changes drastically between *k* =
2 and *k* = 3. Although all 2-locally self-reducible sets belong
to MOD_{6}PH, some 3-locally self-reducible sets are PSPACE-complete.
Furthermore, there exists a 6-locally self-reducible PSPACE-complete
set whose self-reduction is an m-reduction (in fact, a permutation).

We prove all these results by showing that such languages are equivalent in complexity to the problem of multiplying an exponentially long sequence of uniformly generated elements in a finite monoid, and then exploiting the algebraic structure of the monoid.