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:


1. Can we compute $m$ in polynomial time?
2. 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.



Faster multiplication with a restricted set of multiplicands?
This question has already been studied in the literature under the term "word chains". Doing a search on that term will turn up some relevant papers, such as 


<http://dl.acm.org/citation.cfm?id=33329>


<http://www.sciencedirect.com/science/article/pii/0020019089901671>


<http://dl.acm.org/citation.cfm?id=79917>


Basically one cannot get a much better compression (in general) than the one you propose.


Caution: there is a different, unrelated problem also called "word chain" in the literature.


Addendum: Yu. V. Merekin has also worked on this problem, but to my knowledge it has only appeared in Russian.


<http://www.mathnet.ru/php/person.phtml?personid=17890&option_lang=eng>


Addendum 2: And finally, there is a complexity result here:


<https://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf>


although I never managed to understand the proof.


