A transformation semigroup is a pair, where X is a set and S is a semigroup of transformations of X. Here a transformation of X is just a partial function from subset of X to X, not necessarily invertible, and therefore S is simply a set of transformations of X which is closed under composition of functions. The set of all partial functions on a given base set, X, forms a regular semigroup called the semigroup of all partial transformations, typically denoted by. If S includes the identity transformation of X, then it is called a transformation monoid. Obviously any transformation semigroup S determines a transformation monoid M by taking the union of S with the identity transformation. A transformation monoid whose elements are invertible is a permutation group. The set of all transformations of X is a transformation monoid called the full transformation monoid of X. It is also called the symmetric semigroup of X and is denoted by TX. Thus a transformation semigroup is just a subsemigroup of the full transformation monoid of X. If is a transformation semigroup then X can be made into a semigroup action of S by evaluation: This is a monoid action if S is a transformation monoid. The characteristic feature of transformation semigroups, as actions, is that they are effective, i.e., if then s = t. Conversely if a semigroup S acts on a set X by T = s • x then we can define, for s ∈ S, a transformation Ts of X by The map sending s to Ts is injective if and only if is effective, in which case the image of this map is a transformation semigroup isomorphic to S.
Cayley representation
In group theory, Cayley's theorem asserts that any group G is isomorphic to a subgroup of the symmetric group of G, so that G is a permutation group. This theorem generalizes straightforwardly to monoids: any monoid M is a transformation monoid of its underlying set, via the action given by left multiplication. This action is effective because if ax = bx for all x in M, then by taking xequal to the identity element, we have a = b. For a semigroup S without a identity element, we take X to be the underlying set of the monoid corresponding to S to realise S as a transformation semigroup of X. In particular any finite semigroup can be represented as a subsemigroup of transformations of a set X with |X| ≤ |S| + 1, and if S is a monoid, we have the sharper bound |X| ≤ |S|, as in the case of finite groups.
In computer science, Cayley representations can be applied to improve the asymptotic efficiency of semigroups by reassociating multiple composed multiplications. The action given by left multiplication results in right-associated multiplication, and vice versa for the action given by right multiplication. Despite having the same results for any semigroup, the asymptotic efficiency will differ. Two examples of useful transformation monoids given by an action of left multiplication are the functional variation of the differencelist data structure, and the monadic Codensity transformation.
