||This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (July 2013) (Learn how and when to remove this template message)|
In algebra, a transformation semigroup (or composition semigroup) is a collection of 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 anologue of a permutation group.
A transformation semigroup of a set has a tautological semigroup action on that set. Such actions are characterized by being effective, 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.
Transformation semigroups and monoids
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 X to itself, not necessarily invertible, and therefore S is simply a set of transformations of X which is closed under composition of functions. 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. The full transformation monoid is a regular semigroup.
If (X,S) 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) = 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 (X, T) is effective, in which case the image of this map is a transformation semigroup isomorphic to S.
In group theory, Cayley's theorem asserts that any group G is isomorphic to a subgroup of the symmetric group of G (regarded as a set), 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 (or right) multiplication. This action is effective because if ax = bx for all x in M, then by taking x equal to the identity element, we have a = b.
For a semigroup S without a (left or right) 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.
Transformation monoid of an automaton
Let M be a deterministic automaton with state space S and alphabet A. The words in the free monoid A∗ induce transformations of S giving rise to a monoid morphism from A∗ to the full transformation monoid TS. The image of this morphism is the transformation semigroup of M.
- Dominique Perrin; Jean Eric Pin (2004). Infinite Words: Automata, Semigroups, Logic and Games. Academic Press. p. 448. ISBN 978-0-12-532111-2.
- Anderson (2006) p.78
- Anderson (2006) p.81
- Anderson, James A. (2006). Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. ISBN 0-521-61324-8. Zbl 1127.68049.
- Clifford, A.H.; Preston, G.B. (1961). The algebraic theory of semigroups. Vol. I. Mathematical Surveys. 7. Providence, R.I.: American Mathematical Society. ISBN 978-0-8218-0272-4. Zbl 0111.03403.
- Howie, John M. (1995). Fundamentals of Semigroup Theory. London Mathematical Society Monographs. New Series. 12. Oxford: Clarendon Press. ISBN 0-19-851194-9. Zbl 0835.20077.
- Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs, Expositions in Mathematics 29, Walter de Gruyter, Berlin, ISBN 978-3-11-015248-7.