Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Transformation semigroup
Summary
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. There is a correspondence between the two notions.
A transformation semigroup is a pair (X,S), where X is a set and S is a semigroup of transformations of X. Here a transformation of X is just a function from a 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 (or the partial transformation semigroup on X), 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 (or semigroup) of X. It is also called the symmetric semigroup of X and is denoted by TX. Thus a transformation semigroup (or monoid) is just a subsemigroup (or submonoid) of the full transformation monoid of X.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.