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.

  • 1
    $\begingroup$ How does the property of having an inverse make the task trivial? $\endgroup$ – tomasz Jun 21 '12 at 17:48
  • $\begingroup$ When you say sublist, what do you mean? Do you mean $a_i, a_{i+1},...,a_{j-1},a_{j}$ or any sequence of items in the list? $\endgroup$ – Thomas Andrews Jun 21 '12 at 18:19
  • $\begingroup$ Transition semigroups play a role in Markov processes but I'm not sure if that's what you're looking for $\endgroup$ – Cocopuffs Jun 21 '12 at 18:47
  • 2
    $\begingroup$ The cyclic semigroups $(n,m)$, where $n$ and $m$ are positive integers; every element is a power of $x$, with the distinct powers being $x$, $x^2$, $x^3,\ldots,x^n,x^{n+1},\ldots,x^{n+m-1}$, and then $x^{n+m}=x^n$. E.g., $(3,1)$ is the "counting" semigroup "one, two, many". $\endgroup$ – Arturo Magidin Jun 21 '12 at 18:48
  • $\begingroup$ 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$. $\endgroup$ – Ari Jun 23 '12 at 9:18

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?

  • $\begingroup$ I'll probably go with gcd. The others have issues of representation that I'd rather not have to address. Thanks. $\endgroup$ – Ari Jun 23 '12 at 10:04
  • $\begingroup$ @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 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. $\endgroup$ – Fizz Apr 16 '15 at 18:41

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 ;-)

  • $\begingroup$ OP specifically said that words with concatenation are not interesting for this purpose. $\endgroup$ – MJD Jun 21 '12 at 20:53
  • 1
    $\begingroup$ @MarkDominus no, if you represent them in some compressed form, e.g. $a^5b^6a^2$ or via ropes (so the concatenation is fast) or whatever ;-) I was aware of that problem, however, OP explicitly mentioned trees, which have similar drawbacks. But thanks for attention ;-) $\endgroup$ – dtldarek Jun 21 '12 at 22:04
  • $\begingroup$ Some of these are quite interesting (especially ropes, which I wasn't aware of) but generally will require me to explain too much (either about the notion itself or about the representation or about how to perform the computation of a single product) for them to serve as motivating examples which I'd mention in a sentence or two. What is a tree with a hole? I am unfamiliar with the concept. $\endgroup$ – Ari Jun 23 '12 at 10:10
  • $\begingroup$ @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. $\endgroup$ – dtldarek Jun 23 '12 at 10:18

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.

  • $\begingroup$ 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. $\endgroup$ – Fizz Apr 16 '15 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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