5
$\begingroup$

I'm going to give a lecture on Alon and Schieber's Tech Report on computing semigroup products (Optimal Preprocessing for Answering On-Line Product Queries). Basically, given a list of elements $a_1,\ldots,a_n$ and a bound $k$, they show how to preprocess the elements so that later it is possible to efficiently compute the product of any arbitrary sublist $a_i\cdot\ldots\cdot a_j$ by performing only $k$ products.

To motivate this algorithm I am looking for examples of semigroups where: 1. It is plausible that one would have a list of elements and want to compute products of sublists. 2. The semigroup is not a group (since the problem is trivial for groups). 3. The space complexity of the product does not overwhelm the time complexity of computing it directly (e.g., in string concatenation, just copying the result to the output takes the same time as computing it even with no preprocessing).

So far I only have $\min$ and $\max$ and matrix multiplication as examples. I'm looking for something more "sexy", preferably related to Computer Science (perhaps something to do with graphs or trees). Also, for $\min$ and $\max$ there is a better algorithm, so I can't really use them to motivate this algorithm.

  • 0
    By sublist I mean contiguous, as in $a_i, a_{i+1}, a_{i+2},\ldots, a_j$. If you have inverse, just compute all prefix products of the form $P_i=\Pi_{j=1}^ia_j$, as well as inverse products $Q_i=\Pi^{j=i}_1a_j^{-1}$ during preprocessing. Then at query time, the answer for $(i,j)$ is just $Q_{i-1}\cdot P_j$.2012-06-23

3 Answers 3

2

I'm not sure exactly what you're looking for, but here are some semigroup operations:

Do any of these help? Other than being related to computer science, what properties do you want this semigroup to have?

  • 0
    @Ari: Regarding the 2nd bullet, that's actually the two-element Boolean algebra after a bit more thought (on its lattice structure); So pretty famous. See http://en.wikipedia.org/wiki/Semigroup_with_two_elements for some details. On the other hand it also turns out to be a group with a different operation (xor). Also, gcd and lcm actually form a lattice, but it's not a complemented lattice unless the numbers are coprime.2015-04-16
2

Some examples:

  • words with concatenation,
  • natural numbers with addition or multiplication,
  • lattices (e.g. lca/gcd, those are max/min, but hidden),
  • semirings (e.g. take look at this),
  • square matrices,
  • subsets of permutations,
  • non-invertible functions with composition,
  • automatas and languages with union or intersection or composition,
  • mergable heaps (if done properly), priority queues or just plain sets,
  • trees with one hole and composition.

Hope that helps ;-)

  • 0
    @Ari It is a structure that emerges when you shoot off one of tree's branches ;-) Formally, it is a tree with one marked leaf, when you join two trees, you remove the marked leaf and put there there the other tree as a subtree.2012-06-23
2

The composition of functions can be generalized to the composition of binary relations. The composition of binary relations is associative, and they form a semigroup if restricted to relations from $X$ to $X$.

If $X$ is finite, they can be represented by a digraph with loops.

  • 0
    This example seems to meet the other requirements as well; i.e. the product is non-trivial to calculate relative to the space it takes to represent.2015-04-16