Transformation semigroup

In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations (functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transformation (or composition) monoid. This is the semigroup analogue of a permutation group.

A transformation semigroup of a set has a tautological semigroup 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 of Cayley's theorem shows that any semigroup can be realized as a transformation semigroup of some set.

In automata theory, some authors use the term transformation semigroup to refer to a semigroup acting faithfully on a set of "states" different from the semigroup's base set.^[1] There is a correspondence between the two notions.