Concept

Transformation semigroup

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

https://en.wikipedia.org/wiki/Transformation_semigroup

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.

Related courses (1)

MATH-485: Introduction to stochastic PDEs

Stochastic PDEs are used to model systems that are spatially extended and include a random component. This course gives an introduction to this topic, including some general measure theory, some Gauss

Related lectures (13)

Abstract algebra and type classes

Covers abstract algebra concepts using type classes in Scala, including defining monoids, generalizing reduce functions, and typeclass laws.

Explores self-similarity in groups, focusing on Aut(X*) and its subgroups.

Conformal Blocks: Understanding Young Diagrams and Weight States

Covers conformal blocks, Young diagrams, and their significance in weight states.

Related publications (1)

A mealy machine with polynomial growth of irrational degree

We consider a very simple Mealy machine ( two nontrivial states over a two-symbol alphabet), and derive some properties of the semigroup it generates. It is an infinite, finitely generated semigroup, and we show that the growth function of its balls behave ...

2008

Related concepts (6)

Semiautomaton

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. Associated with any semiautomaton is a monoid called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which acts on the set of states Q.

Green's relations

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?'" (Howie 2002).

Bicyclic semigroup

In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. It is perhaps most easily understood as the syntactic monoid describing the Dyck language of balanced pairs of parentheses. Thus, it finds common applications in combinatorics, such as describing binary trees and associative algebras. The first published description of this object was given by Evgenii Lyapin in 1953.