Transformation semigroup
From Wikipedia, the free encyclopedia
In mathematics, a transformation semigroup is a collection of mappings on a set X closed under composition. It is a construct occurring in semigroup theory and analogous to the standard representation of a group as a subgroup of permutations on a set X.
Contents |
[edit] Definition
A transformation semigroup (X,S) consists of a set X and a semigroup S of functions ("transformations") mapping X to itself. In this context, each member of S is called a transformation on the set X and is just a function f: X → X. Each element s of S transforms x in X into a "next state" xs in X, so each semigroup element s corresponds to a mapping φs: X → X. Notice that composite function st is defined by x(st) = (xs)t for all states x in X. The definition requires closure, i.e. if s and t are S, then so is the composite function st determined by applying s and then t to an element of X.
It is important to note that the transformations in (X,S) may be, but are not required to be, permutations. If all of them are permutations and for each member of S the inverse of each member of S is also in S, then we have a permutation group. Some authors write xs or (x)s for transformation s applied to x, others write sx or s(x). The semigroup S under function composition is not necessarily commutative, since st and ts may be different transformations of X, just as f(g(x)) ≠ g(f(x)) in general.
[edit] Examples
Example: Taking the set FX of all functions from X to X yields a transformation semigroup (X,FX), called the full transformation semigroup on X.
Example: Transformation semigroup of an automaton. If A is a deterministic automaton, then each finite sequence of input letters to A determines a transformation on the set states Q of the automaton. These transformations comprise a semigroup TA, the characteristic semigroup of the automaton, and (Q, TA) is a transformation semigroup. Note that TA is necessarily finite if Q is.
[edit] Representation Theorem
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). Thus G can be represented as a group of permutations on some underlying set X of letters or "states". Cayley's theorem implies that |X| ≤ |G| so that at most |G| states are needed. The corresponding result to the above for semigroups is that every semigroup S can be represented as a subsemigroup of transformations on a state set X with |X| ≤ |S| + 1. If S has a left identity e then we can let X = S; otherwise, we formally adjoin a left identity e to X to obtain X = S ∪ {e}.
[edit] Applications to computer science
Transformation semigroups are of essential importance for the structure theory of finite state machines or automata. They also occur in the theory of digital networks by viewing a state machine as a network composition of coupled smaller state machines, of which there are five basic types (since there are 5 non-isomorphic semigroups of order 2, with clear engineering interpretations, see [1] ). Krohn-Rhodes Theory, sometimes also called algebraic automata theory, gives striking and powerful decomposition results for finite transformation semigroups by cascading simpler components.
