Transformation semigroup

Last updated December 27, 2022

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.

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 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 ${\mathcal {PT}}_{X}$ .^[2]

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 T_X. Thus a transformation semigroup (or monoid) is just a subsemigroup (or submonoid) 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){\text{ for }}s\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{\text{ for all }}x\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, 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 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 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.^[3]^: 21

In computer science

In computer science, 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).^[4]

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 T_S. The image of this morphism is the transformation semigroup of M.^[3]^: 78

For a regular language, the syntactic monoid is isomorphic to the transformation monoid of the minimal automaton of the language.^[3]^: 81

Related Research Articles

In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism group of the structure. It is said that the group acts on the space or structure. If a group acts on a structure, it will usually also act on objects built from that structure. For example, the group of Euclidean isometries acts on Euclidean space and also on the figures drawn in it. For example, it acts on the set of all triangles. Similarly, the group of symmetries of a polyhedron acts on the vertices, the edges, and the faces of the polyhedron.

In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type. The word homomorphism comes from the Ancient Greek language: ὁμός meaning "same" and μορφή meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German ähnlich meaning "similar" to ὁμός meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925).

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.

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. The group of all permutations of a set M is the symmetric group of M, often written as Sym(M). The term permutation group thus means a subgroup of the symmetric group. If M = {1, 2, ..., n} then Sym(M) is usually denoted by S_n, and may be called the symmetric group on n letters.

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

In mathematics, the concept of an inverse element generalises the concepts of opposite and reciprocal of numbers.

In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group $G$ is isomorphic to a subgroup of a symmetric group. More specifically, $G$ is isomorphic to a subgroup of the symmetric group $whose elements are the permutations of the underlying set of G . Explicitly,$

In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.

In mathematics and computer science, the Krohn–Rhodes 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 to finite aperiodic semigroups and finite simple groups that are combined in a feedback-free manner.

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A^∗. The free semigroup on A is the subsemigroup of A^∗ containing all elements except the empty string. It is usually denoted A⁺.

In algebra and theoretical computer science, an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in such a way that the product of two elements of the semigroup is associated with the composite of the two corresponding transformations. The terminology conveys the idea that the elements of the semigroup are acting as transformations of the set. From an algebraic perspective, a semigroup action is a generalization of the notion of a group action in group theory. From the computer science point of view, semigroup actions are closely related to automata: the set models the state of the automaton and the action models transformations of that state in response to inputs.

In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951. John Mackintosh Howie, a prominent semigroup theorist, described this work as "so all-pervading that, on encountering a new semigroup, almost the first question one asks is 'What are the Green relations like?'". The relations are useful for understanding the nature of divisibility in a semigroup; they are also valid for groups, but in this case tell us nothing useful, because groups always have divisibility.

In group theory, an inverse semigroupS is a semigroup in which every element x in S has a unique inversey in S in the sense that x = xyx and y = yxy, i.e. a regular semigroup in which every element has a unique inverse. Inverse semigroups appear in a range of contexts; for example, they can be employed in the study of partial symmetries.

In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function.

In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered as unary operator, exhibits certain fundamental properties of the operation of taking the inverse in a group: uniqueness, double application "cancelling itself out", and the same interaction law with the binary operation as in the case of the group inverse. It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.

In mathematics, a semigroup with two elements is a semigroup for which the cardinality of the underlying set is two. There are exactly five distinct nonisomorphic semigroups having two elements:

In computer science, more precisely in automata theory, a rational set of a monoid is an element of the minimal class of subsets of this monoid that contains all finite subsets and is closed under union, product and Kleene star. Rational sets are useful in automata theory, formal languages and algebra.

In mathematics, a rational monoid is a monoid, an algebraic structure, for which each element can be represented in a "normal form" that can be computed by a finite transducer: multiplication in such a monoid is "easy", in the sense that it can be described by a rational function.

In mathematics, and more precisely in semigroup theory, a variety of finite semigroups is a class of semigroups having some nice algebraic properties. Those classes can be defined in two distinct ways, using either algebraic notions or topological notions. Varieties of finite monoids, varieties of finite ordered semigroups and varieties of finite ordered monoids are defined similarly.

References

↑ Dominique Perrin; Jean Eric Pin (2004). Infinite Words: Automata, Semigroups, Logic and Games. Academic Press. p. 448. ISBN 978-0-12-532111-2.
↑ Alfred Hoblitzelle Clifford; G. B. Preston (1967). The Algebraic Theory of Semigroups. Volume II. American Mathematical Soc. p. 254. ISBN 978-0-8218-0272-4.
1 2 3 Anderson, James A. (2006). Automata Theory with Modern Applications. With contributions by Tom Head. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511607202. ISBN 978-0-521-61324-8. Zbl 1127.68049.
↑ Rivas, Exequiel; Jaskelioff, Mauro (2017). "Notions of Computation as Monoids". Journal of Functional Programming. 27 (e21). arXiv: 1406.4823 . doi:10.1017/S0956796817000132.

Clifford, A.H.; Preston, G.B. (1961). The algebraic theory of semigroups. Vol. I. Mathematical Surveys. Vol. 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. Vol. 12. Oxford: Clarendon Press. ISBN 978-0-19-851194-6. 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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[PerrinPin2004-1] Dominique Perrin; Jean Eric Pin (2004). Infinite Words: Automata, Semigroups, Logic and Games. Academic Press. p. 448. ISBN 978-0-12-532111-2.

[CliffordPreston1967-2] Alfred Hoblitzelle Clifford; G. B. Preston (1967). The Algebraic Theory of Semigroups. Volume II. American Mathematical Soc. p. 254. ISBN 978-0-8218-0272-4.

[JAA-3] 1 2 3 Anderson, James A. (2006). Automata Theory with Modern Applications. With contributions by Tom Head. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511607202. ISBN 978-0-521-61324-8. Zbl 1127.68049.

[4] Rivas, Exequiel; Jaskelioff, Mauro (2017). "Notions of Computation as Monoids". Journal of Functional Programming. 27 (e21). arXiv: 1406.4823 . doi:10.1017/S0956796817000132.

[1]

[2]

[3]

[4]

Transformation semigroup

Contents