HOME

TheInfoList



OR:

In
algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary ...
, a transformation semigroup (or composition semigroup) is a collection of transformations ( functions from a set to itself) that is
closed Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...
under
function composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
. If it includes the
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
, it is a
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
, called a transformation (or composition) monoid. This is the
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
analogue of a
permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...
. 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 In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group is isomorphic to a subgroup of a symmetric group. More specifically, is isomorphic to a subgroup of the symmetric group \operatorname(G) whose elem ...
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 subset of ''X'' to ''X'', not necessarily invertible, and therefore ''S'' is simply a set of transformations of ''X'' which is
closed Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...
under composition of functions. The set of all
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
s 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 \mathcal_X. 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 In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...
. 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 ''T''''X''. Thus a transformation semigroup (or monoid) is just a
subsemigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
(or
submonoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids ...
) of the full transformation monoid of ''X''. If (''X'',''S'') is a transformation semigroup then ''X'' can be made into a semigroup action of ''S'' by evaluation: : s\cdot x = s(x)\texts\in S, x\in X. This is a monoid action if ''S'' is a transformation monoid. The characteristic feature of transformation semigroups, as actions, is that they are ''faithful'', i.e., if : s\cdot x = t\cdot x\textx\in X, 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 ''T''''s'' of ''X'' by : T_s (x) = T(s,x).\, The map sending ''s'' to ''T''''s'' is injective if and only if (''X'', ''T'') is faithful, in which case the image of this map is a transformation semigroup isomorphic to ''S''.


Cayley representation

In
group theory In abstract algebra, group theory studies the algebraic structures known as groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen ...
,
Cayley's theorem In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group is isomorphic to a subgroup of a symmetric group. More specifically, is isomorphic to a subgroup of the symmetric group \operatorname(G) whose elem ...
asserts that any group ''G'' is isomorphic to a subgroup of the
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
of ''G'' (regarded as a set), so that ''G'' is a
permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...
. 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 faithful 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 In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
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 group Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or ma ...
s.


In computer science

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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 the difference list data structure, and the monadic Codensity transformation (a Cayley representation of a monad, which is a monoid in a particular monoidal functor category).


Transformation monoid of an automaton

Let ''M'' be a deterministic
automaton An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...
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 ''T''''S''. The image of this morphism is the transformation semigroup of ''M''. For a regular language, the
syntactic monoid In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L. Syntactic quotient The free monoid on a given set is the monoid whose elements are all the strings of ze ...
is isomorphic to the transformation monoid of the
minimal automaton In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equiva ...
of the language.


See also

* Semiautomaton *
Krohn–Rhodes theory In mathematics and computer science, the Krohn–Rhodes theory (or algebraic automata theory) is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These components correspond ...
* Symmetric inverse semigroup *
Biordered set A biordered set (otherwise known as boset) is a mathematical object that occurs in the description of the structure of the set of idempotents in a semigroup. The set of idempotents in a semigroup is a biordered set and every biordered set is the ...
*
Special classes of semigroups In mathematics, a semigroup is a nonempty set together with an associative binary operation. A special class of semigroups is a class of semigroups satisfying additional properties or conditions. Thus the class of commutative semigroups consists ...
*
Composition ring In mathematics, a composition ring, introduced in , is a commutative ring (''R'', 0, +, −, ·), possibly without an identity 1 (see non-unital ring), together with an operation : \circ: R \times R \rightarrow R such that, for any three e ...


References

* * * 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. Semigroup theory