Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product $$ p=b_1 b_2 \cdots b_n$$ where each $b_i\in A$. Clearly $n-1$ multiplications suffice to compute $p$; can we do it with fewer?
Let $m=m(b_1,...,b_n)$ be the minimum number of multiplications required to compute $p$. My specific questions are:
- Can we compute $m$ in polynomial time?
- Can we answer question #1 constructively, i.e. actually figure out which $m$ terms can be multiplied together to compute $p$? If not, can we do it with some approximation guarantee (like "at worst we use $2m$ terms"?)
The interesting case (for my application, anyway) occurs when $n\gg k$ (so there are many common subexpressions) but the semigroup is noncommutative (so you cannot simply rearrange terms and use repeated doubling).
Let me outline one simple (but insufficient) approach. Suppose that we begin by computing all products of (not necessarily distinct) pairs from $A$. Then we can compute $p$ with $k^2+(\lceil n/2 \rceil -1)$ multiplications by multiplying the terms two at a time. If $k^2\ll n$, then we have essentially halved the number of multiplications. Analogous reasoning can be extended to provide roughly an $\lfloor \log_k(n)-\log_k(\log_k(n)) \rfloor -1$ improvement in the number of multiplications. However, for highly repetitive strings we could do much better still.
This problem arose in the context of parallel inference algorithms for hidden Markov models; the noncommutative semigroup in question consists of non-negative matrices over the reals.