Inalgebra, atransformation semigroup (orcomposition semigroup) is a collection oftransformations (functions from a set to itself) that isclosed underfunction composition. If it includes theidentity function, it is amonoid, called atransformation (orcomposition)monoid. This is thesemigroup analogue of apermutation group.

A transformation semigroup of a set has a tautologicalsemigroup action on that set. Such actions are characterized by being faithful, i.e., if two elements of the semigroup have the same action, then they are equal.

An analogue ofCayley's theorem shows that any semigroup can be realized as a transformation semigroup of some set.

Inautomata theory, some authors use the termtransformation semigroup to refer to a semigroupacting faithfully on a set of "states" different from the semigroup's base set.^[1] There isa correspondence between the two notions.

Atransformation semigroup is a pair (X,S), whereX is a set andS is a semigroup of transformations ofX. Here atransformation ofX is just afunction from a subset ofX toX, not necessarily invertible, and thereforeS is simply a set of transformations ofX which isclosed undercomposition of functions. The set of allpartial functions on a given base set,X, forms aregular semigroup called the semigroup of all partial transformations (or thepartial transformation semigroup onX), typically denoted by${\displaystyle {\mathcal{P}\mathcal{T}}_X}$.^[2]

IfS includes the identity transformation ofX, then it is called atransformation monoid. Any transformation semigroupS determines a transformation monoidM by taking the union ofS with the identity transformation. A transformation monoid whose elements are invertible is apermutation group.

The set of all transformations ofX is a transformation monoid called thefull transformation monoid (orsemigroup) ofX. It is also called thesymmetric semigroup ofX and is denoted byT_X. Thus a transformation semigroup (or monoid) is just asubsemigroup (orsubmonoid) of the full transformation monoid ofX.

If (X,S) is a transformation semigroup thenX can be made into asemigroup action ofS by evaluation:

${\displaystyle s\cdot x=s(x)\text{ for }s\in S,x\in X.}$

This is a monoid action ifS is a transformation monoid.

The characteristic feature of transformation semigroups, as actions, is that they arefaithful, i.e., if

${\displaystyle s\cdot x=t\cdot x\text{ for all }x\in X,}$

thens =t. Conversely if a semigroupS acts on a setX byT(s,x) =s •x then we can define, fors ∈S, a transformationT_s ofX by

${\displaystyle T_s(x)=T(s,x).}$

The map sendings toT_s is injective if and only if (X, T) is faithful, in which case the image of this map is a transformation semigroup isomorphic toS.

Ingroup theory,Cayley's theorem asserts that any groupG is isomorphic to a subgroup of thesymmetric group ofG (regarded as a set), so thatG is apermutation group. This theorem generalizes straightforwardly to monoids: any monoidM is a transformation monoid of its underlying set, via the action given by left (or right) multiplication. This action is faithful because ifax =bx for allx inM, then by takingx equal to the identity element, we havea =b.

For a semigroupS without a (left or right) identity element, we takeX to be the underlying set of themonoid corresponding toS to realiseS as a transformation semigroup ofX. In particular any finite semigroup can be represented as asubsemigroup of transformations of a setX with |X| ≤ |S| + 1, and ifS is a monoid, we have the sharper bound |X| ≤ |S|, as in the case offinite groups.^[3]: 21

Incomputer 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 thedifference list data structure, and the monadic Codensity transformation (a Cayley representation of amonad, which is a monoid in a particularmonoidalfunctor category).^[4]

LetM be a deterministicautomaton with state spaceS and alphabetA. The words in thefree monoidA^∗ induce transformations ofS giving rise to amonoid morphism fromA^∗ to the full transformation monoidT_S. The image of this morphism is the transformation semigroup ofM.^[3]: 78

For aregular language, thesyntactic monoid is isomorphic to the transformation monoid of theminimal automaton of the language.^[3]: 81

• Endofunction
• Semiautomaton
• Krohn–Rhodes theory
• Symmetric inverse semigroup
• Biordered set
• Special classes of semigroups
• Composition ring

• Clifford, A.H.; Preston, G.B. (1961).The algebraic theory of semigroups. Vol. I. Mathematical Surveys. Vol. 7. Providence, R.I.:American Mathematical Society.ISBN 978-0-8218-0272-4.Zbl 0111.03403.{{cite book}}:ISBN / Date incompatibility (help)
• Howie, John M. (1995).Fundamentals of Semigroup Theory. London Mathematical Society Monographs. New Series. Vol. 12. Oxford:Clarendon Press.ISBN 978-0-19-851194-6.Zbl 0835.20077.
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000),Monoids, Acts and Categories: with Applications to Wreath Products and Graphs, Expositions in Mathematics29, Walter de Gruyter, Berlin,ISBN 978-3-11-015248-7.

• Semigroup theory

• CS1 errors: ISBN date