What are some (or even one) interesting examples of (non-group) semigroups?

Question

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.

Answer 1

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

• Multiplication of polynomials.

• Conjunction of logical expressions which are in disjunctive normal form.

• Cartesian product of graphs, or other graph products.

• Unions of finite sets.

• Greatest common divisor or least common multiple of integers.

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

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

Answer 3

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.