Let us say I have a semigroup M and its basis B. I know which elements of B commute.

What is the most efficient way to do multiplication in such a semigroup?

Essentially, this is a question of how to reduce "ABAAAXBCAAB" to "AAAABXAABBC" knowing that A, B and C commute with each other but not with X (after such a transform I can, for example, compute AAAA as (A^2)^2, or even store pre-computed powers of each element of B).

  • $\begingroup$ What is your cost model? Is "AABC" meant to be more efficient that "CAAB"? $\endgroup$ Commented Sep 9, 2010 at 8:09
  • $\begingroup$ My cost model is that I want to minimize the number of multiplications, but the multiplications themselves are equivalent in cost. $\endgroup$
    – jkff
    Commented Sep 9, 2010 at 8:16
  • 1
    $\begingroup$ If the semigroup is generated by a single element A, the problem of finding the most efficient way to compute A^n is equivalent to finding a minimum-length addition chain ending with n, which is discussed in cstheory.stackexchange.com/questions/912/…. My understanding from that question is that even in this case, we do not know how to find the optimal way in time polynomial in n, although this is computable exactly in time 2^{O(log n log log n)} and (1+o(1))-approximable in time polylogarithmic in n. $\endgroup$ Commented Sep 9, 2010 at 11:37
  • 1
    $\begingroup$ I suspect that rearranging a product so that the same generators become adjacent as much as possible does not necessarily minimizes the number of multiplications required to compute the product. Here is what might be a counterexample. Consider the semigroup generated by A, B and C where the only relation is that A and B commute. Suppose that we want to compute P=AB⋅C⋅(AB)^2⋅C⋅(AB)^4⋅C⋅…⋅C⋅(AB)^{2^k}. (more) $\endgroup$ Commented Sep 9, 2010 at 11:58
  • 3
    $\begingroup$ If you are satisfied with your solution, I have no complaint about it. However, if you are looking for something more, I suggest you to revise the question so that it is clear that you are not only interested in finding the most efficient way to compute a product but somewhat efficient ways, stating the exact meaning of this somewhat efficient you are interested in. $\endgroup$ Commented Sep 9, 2010 at 14:01

1 Answer 1


Okay, I've given it a bit of thought and I see that the algorithm is very easy.

Example: Let % denote "commutes". Let A % B, A % C, B % C, B % X.


Let us keep a "result", an "active multiset" and a "remaining suffix". Let us append a special "$" symbol that commutes with noone onto the string.

Invariant: the product of "result", active multiset and the remaining suffix equals the product of original string.

Invariant: all items in the active multiset commute.

At each new element of the suffix, drop elements from the active multiset that don't commute with it into the product, and insert the element into the multiset.

(1, {}, ABAAXCBA$) ->
(1, {A:1}, BAAXCBA$) -> 
(1, {A:1, B:1}, AAXCBA$) ->
(1, {A:2, B:1}, AXCBA$) ->
(1, {A:3, B:1}, XCBA$) -> (drop A^3)
(A^3, {B:1, X:1}, CBA$) ->
(A^3 X, {B:1, C:1}, BA$) ->
(A^3 X, {B:2, C:1}, A$) ->
(A^3 X, {B:2, C:1, A:1}, $) ->
(A^3 X B^2 C A, {$}, )

This version has at most O(|A|) (size of alphabet) overhead per input symbol and it does an optimal number of multiplications.

  • $\begingroup$ To the downvoter: care to elaborate about the reason? $\endgroup$
    – jkff
    Commented Sep 10, 2010 at 5:28
  • $\begingroup$ If I understand the algorithm, it is not optimal. For AABB, where A & B freely commute, your algorithm appears to require three multiplications, where only two are required (let x=AB in xx). I'm guessing the downvoter didn't like you presenting an answer without any attempt to justify its optimality. $\endgroup$ Commented Sep 11, 2010 at 14:48
  • $\begingroup$ I'm the downvoter. Why should we believe your algorithm computes optimal results? In particular, how does it optimize the number of multiplications needed to compute AAAAAAAAAAAAAAAAAAAAAAAAAAA? (On the other hand, you haven't told us exactly what "optimal" means.) $\endgroup$
    – Jeffε
    Commented Sep 12, 2010 at 23:26
  • $\begingroup$ Okay, you're right. $\endgroup$
    – jkff
    Commented Sep 13, 2010 at 17:41

Your Answer

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

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