Faster multiplication with a restricted set of multiplicands?

Question

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.

Answer 1

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.

Answer 2

You can try a dynamic programming approach as in this example of optimal parenthesising chain products of matrices.

Specifically, build bottom-up dynamic programming table, as in the above example, by recording the "costs" of multiplications with different parenthesisations. The "cost" would be different than in the case of matrix chains, but the overall approach may work.

EDIT:

You may want to try suffix trees to identify repreated substrings. Suffix trees have been used in Lempel-Ziv compression algorithms, among other things.

LZ compression creates a "dictionary" of repeated patterns so that in the compressed output the repeated pattern would be replaced by a dictionary reference that contains it. At the decompression step you retrieve the pattern from the dictionary.

You can do something very similar, except that in the compression step you add the computed value of the pattern to the dictionary, and at the decompression step you retrieve that pre-computed value.