Optimizing multiplication in a partly commutative semigroup 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).
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.

Compute ABAAXCBA:

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$) -&gt;
(1, {A:1}, BAAXCBA$) -&gt; 
(1, {A:1, B:1}, AAXCBA$) -&gt;
(1, {A:2, B:1}, AXCBA$) -&gt;
(1, {A:3, B:1}, XCBA$) -&gt; (drop A^3)
(A^3, {B:1, X:1}, CBA$) -&gt;
(A^3 X, {B:1, C:1}, BA$) -&gt;
(A^3 X, {B:2, C:1}, A$) -&gt;
(A^3 X, {B:2, C:1, A:1}, $) -&gt;
(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.