1. Background and Definitions

1.1 Semigroups and closure under composition

A semigroup is an algebraic structure consisting of a set together with an associative binary operation. In many mathematical settings, the operation arises from composing processes, relations, or functions. When the elements of the semigroup can be interpreted as operations, associativity corresponds to performing them in sequence: doing “first then second then third” yields the same result as “(first then second) then third.”

Closure under the chosen operation is essential: it guarantees that composing any two elements of the collection produces another element that still belongs to the same structure.

1.2 Transformations on a set

Let \(X\) be a nonempty set. A transformation of \(X\) is a function \(f \colon X \to X\). Transformations can be composed: for transformations \(f,g\), their product is \(f\circ g\), meaning \((f\circ g)(x)=f(g(x))\). Under this operation, transformations form an associative structure because function composition is associative.

A key feature distinguishing transformation semigroups from groups is that transformations need not be invertible; not every map admits a two-sided inverse.

1.3 Transformation semigroups as subsemigroups of \(\mathcal{T}(X)\)

Denote by \(\mathcal{T}(X)\) the set of all functions \(X\to X\). With multiplication defined by composition, \(\mathcal{T}(X)\) becomes a semigroup; in fact it is the largest transformation semigroup on \(X\). A transformation semigroup on \(X\) is any subset \(S\subseteq \mathcal{T}(X)\) such that:

  1. \(S\) is closed under composition: if \(f,g\in S\), then \(f\circ g\in S\);
  2. associativity holds automatically, since it comes from function composition.

1.4 Generating sets and the subsemigroup they define

Transformation semigroups are often described via generators. Given a subset \(G\subseteq \mathcal{T}(X)\), the smallest subsemigroup containing \(G\) is the set of all finite compositions of elements of \(G\). This generated collection can be written as \[ \langle G\rangle=\{g_{1}\circ g_{2}\circ\cdots\circ g_{k} \mid k\ge 1,\ g_i\in G\}. \] In many applications, generators represent elementary operations, transitions, or basic update rules. Studying the structure of \(\langle G\rangle\) provides information about the behavior achievable by repeating those elementary operations.

2. Fundamental Examples

2.1 Full transformation semigroup \(\mathcal{T}(X)\)

The full transformation semigroup \(\mathcal{T}(X)\) contains every transformation \(X\to X\). It is maximal with respect to inclusion among transformation semigroups on \(X\). Its size equals \(X^{X}\), reflecting the number of functions from \(X\) to itself.

Because it is “as large as possible,” \(\mathcal{T}(X)\) serves as a benchmark: any other transformation semigroup on the same set is a subsemigroup of \(\mathcal{T}(X)\). Many phenomena—non-invertibility, idempotents, and orbit collapse—already occur inside this maximal example.

2.2 Permutation semigroups and relation to groups

If one restricts to transformations that are bijections, one obtains the symmetric group \(\mathrm{Sym}(X)\). A permutation semigroup is a subsemigroup of \(\mathrm{Sym}(X)\). Since every bijection is invertible, any subsemigroup of \(\mathrm{Sym}(X)\) that is closed under composition is automatically closed under inverses as well, hence becomes a group.

Thus, permutation semigroups illustrate how transformation semigroups generalize group symmetry: allowing non-bijective maps enlarges the algebraic world beyond groups.

2.3 Monogenic transformation semigroups

A monogenic transformation semigroup is generated by a single transformation \(t\). Such a semigroup consists of the iterates \(\{t,t^{2},t^{3},\dots\}\) (and possibly the identity if it appears as a power). The structure of a monogenic semigroup is closely tied to the functional graph of \(t\), where every element eventually enters a periodic cycle.

In finite settings, iterating a map eventually yields repetition among powers, so the monogenic semigroup typically exhibits a “tail then cycle” behavior.

2.4 Constant maps and idempotent-generated cases

A constant map sends every element of \(X\) to a fixed point \(c\in X\). Composing a constant map with any transformation produces a constant map, and composing on the other side often yields a transformation with image contained in \(\{c\}\). Constant maps are therefore strong building blocks for semigroups: once present, they tend to collapse the set’s structure rapidly.

An idempotent transformation satisfies \(e\circ e=e\). Constant maps are idempotent. Semigroups generated by idempotents (or containing many idempotents) can often be analyzed through the geometry of their images and fixed points, since idempotents behave like “projections” onto stabilized subsets.

2.5 Semigroups from directed graphs and adjacency-induced maps

Transformation semigroups can be built from directed graphs. Given a directed graph with vertex set \(X\), one can associate to each vertex (or each edge-labeled rule) a transformation that updates a state according to outgoing edges. More generally, when edges are labeled by operations, each label can induce a function \(X\to X\) mapping a current vertex to the endpoint determined by that label (when defined deterministically).

The generated transformation semigroup then captures the set of state evolutions achievable by successive graph-driven updates.

3. Green’s Relations and Green Structure

3.1 \(\mathcal{L}\), \(\mathcal{R}\), and \(\mathcal{H}\) relations

Green’s relations partition a semigroup according to how elements generate principal ideals. For a semigroup \(S\), the relation \(\mathcal{L}\) compares elements with the same principal left ideal: \(a\mathcal{L}b\) when \(Sa=Sb\). Similarly, \(\mathcal{R}\) uses right ideals: \(a\mathcal{R}b\) when \(aS=bS\). Their intersection \(\mathcal{H}=\mathcal{L}\cap\mathcal{R}\) captures elements sharing both left and right ideal behavior.

In transformation semigroups, these ideal notions correspond to structural properties of images and preimages under the transformations. They provide an organized way to classify elements without directly listing all maps.

3.2 \(\mathcal{D}\) and \(\mathcal{J}\) relations

The relation \(\mathcal{D}\) is defined as \(\mathcal{D}=\mathcal{L}\circ\mathcal{R}\), meaning two elements are \(\mathcal{D}\)-related if they can be connected through a chain mixing left and right ideal equality. The relation \(\mathcal{J}\) is based on two-sided ideals: \(a\mathcal{J}b\) when \(SaS=SbS\).

For finite semigroups, \(\mathcal{D}\) and \(\mathcal{J}\) often coincide, which simplifies classification. In the transformation setting, these relations frequently align with coarse measures such as rank (size of the image), though finer distinctions still exist.

3.3 Principal ideals and orbit-style interpretations

Principal ideals can be interpreted in terms of reachability through left or right multiplication. For transformation semigroups, left multiplication by an element corresponds to changing the “output side” of a map, while right multiplication corresponds to altering the “input side.”

This viewpoint yields orbit-like interpretations: sets of elements obtainable by composing on one side can be understood as families of transformations that share similar coverage properties over \(X\). Such interpretations are helpful for visualizing Green partitions.

3.4 Maximal subgroups at idempotents

In a general semigroup, maximal subgroups occur naturally “near” idempotents. For an idempotent \(e\), one considers the \(\mathcal{H}\)-class containing \(e\); under appropriate conditions, this \(\mathcal{H}\)-class forms a group with identity \(e\).

In transformation semigroups, these local groups often describe the reversible behavior inside the stabilized structure determined by \(e\). Idempotents thus serve as anchors: they organize both the global semigroup decomposition and the internal symmetry that remains after collapse.

4. Idempotents and Regularity

4.1 Idempotent transformations and their roles

Idempotent transformations \(e\) satisfy \(e(e(x))=e(x)\) for all \(x\). Operationally, applying \(e\) twice is the same as applying it once. In a finite transformation semigroup, idempotents often function like stabilization steps: after one application, further applications do not change the image.

Many structural results in semigroup theory leverage idempotents because they let one reason using fixed points and stabilized subsets rather than arbitrary maps.

4.2 Regular semigroups and characterization via inverses in semigroups

A semigroup element \(a\) is called regular if there exists \(b\) in the semigroup such that \[ a = aba. \] The element \(b\) behaves like a generalized inverse relative to \(a\). A semigroup is regular if every element is regular. Regularity is weaker than invertibility: \(b\) need not satisfy \(bab=b\), and \(a\) may be far from a bijection.

Transformation semigroups provide concrete instances of regularity: some maps admit “back-and-forth” compositional identities even when they are not permutations.

4.3 Inverse semigroups vs general transformation semigroups

An inverse semigroup is a stronger notion where every element has a unique inverse satisfying both \(aba=a\) and \(bab=b\). Transformation semigroups are not generally inverse, but inverse semigroups can be realized using restricted kinds of partial transformations or bijections between subsets.

Comparing inverse semigroups with general transformation semigroups highlights a spectrum: full transformation semigroups allow extensive non-reversibility, while inverse semigroups enforce controlled reversibility.

4.4 Green’s lemma and idempotent-based reasoning

Green’s lemma relates the behavior of idempotents inside \(\mathcal{H}\)-classes to regularity and group structures. In practical terms, it supports arguments where one first locates an idempotent in a given ideal class and then uses that idempotent to derive properties of the surrounding elements.

For transformation semigroups, this often translates into converting questions about arbitrary compositions into questions about how idempotent maps partition \(X\) into stabilized images and preimages.

5. Reachability and Automata Connections

5.1 Transition semigroups of deterministic finite automata

A deterministic finite automaton (DFA) with state set \(X\) has input symbols that induce state transition functions \(X\to X\). Composing symbol-induced transitions according to an input word yields another transformation of the same form. The set of all transformations obtainable from all input words forms the transition semigroup of the automaton.

This connection makes transformation semigroups a natural algebraic model of reachability and computation by repeated updates: the semigroup encodes all possible behaviors under arbitrary inputs.

5.2 Word actions and the induced semigroup homomorphism

Let the automaton alphabet be \(\Sigma\). Each symbol \(a\in\Sigma\) defines a transformation \(t_a\) on \(X\). For a word \(w=a_1a_2\cdots a_k\), the induced transformation is \(t_{a_k}\circ \cdots \circ t_{a_1}\) (depending on convention). The mapping from words under concatenation to transformations under composition is a homomorphism from the free monoid \(\Sigma^*\) into \(\mathcal{T}(X)\).

The image of this homomorphism is precisely the transition semigroup, so the algebra reflects how the language’s prefixes act on states.

5.3 Synchronizing transformations and reset behavior (conceptual)

A DFA is often analyzed for whether it can be driven into a single state regardless of the starting point. Transformation semigroup language interprets this as the existence of a transformation with image of size one—effectively, a transformation that acts like a reset. Such elements are closely connected to constant maps and, more generally, to transformations whose repeated application collapses structure.

“Synchronization” is thus a property of which ranks and collapse behaviors appear inside the transition semigroup.

5.4 Action on subsets and induced semigroups

Beyond acting on individual states, one can examine how the automaton acts on subsets of states. Given a transformation \(f\colon X\to X\), there is a natural induced action on a subset \(A\subseteq X\) by sending it to \(f(A)=\{f(x):x\in A\}\). The induced maps on the power set generate a semigroup that reflects collective reachability properties, commonly used in determinization-like constructions and in analyzing uncertainty propagation.

This subset action provides a bridge between algebraic structure and combinatorial state-set dynamics.

6. Representations and Kernels of Transformations

6.1 Image sets, rank, and transformation “size”

For a transformation \(f\colon X\to X\), the image is \(f(X)\), and its cardinality \(\mathrm{rank}(f)=f(X)\) is a basic quantitative invariant. Rank measures how much information the transformation preserves: higher rank means more distinct outputs, while low rank indicates stronger collapse.

In many contexts, rank controls coarse classification within Green’s relations, and it is central in algorithms that track how repeated compositions shrink images.

6.2 Kernel partitions and congruence viewpoint

The kernel of \(f\) can be viewed as an equivalence relation on \(X\): two elements \(x,y\in X\) are equivalent if \(f(x)=f(y)\). This kernel equivalence partitions the domain into fibers of the map.

From a semigroup perspective, kernels connect to congruences and refinement/coarsening phenomena: composing transformations corresponds to systematically combining information about how preimages are merged and redistributed.

6.3 Rank multiplication properties and monotonicity phenomena

When composing transformations, ranks behave in a constrained manner. Typically, the rank of \(f\circ g\) cannot exceed the rank of \(f\), because the output of \(g\) is fed into \(f\), and any collapse induced by \(g\) limits distinct results. Such monotonicity principles help predict how quickly a semigroup can produce low-rank elements.

Although exact rank evolution depends on the particular maps, these inequalities and monotonic trends are routinely used to bound lengths of words needed to achieve a desired image size.

6.4 Faithful actions and equivalent representations

A transformation semigroup can sometimes be represented faithfully by letting it act on a set whose elements correspond to states of an abstract system. Two semigroup actions are often considered equivalent when they preserve the same transformation behavior up to isomorphism of the acting sets.

Faithful representations are important because they allow translating algebraic questions into questions about explicit functions on a concrete set, where rank, kernels, and fixed points can be computed or reasoned about directly.

7. Structural Theorems and Decompositions

7.1 Divisibility and subquotients of transformation semigroups

Semigroups are compared using divisibility notions such as taking homomorphic images and subsemigroups. A semigroup \(T\) is a divisor of \(S\) (informally) if \(T\) can be obtained from \(S\) by first restricting to a part and then applying a homomorphism, or by similar two-step constructions.

In transformation semigroups, divisibility corresponds to extracting smaller systems or quotienting by equivalence relations, reflecting how complex behavior can be built from or reduced to simpler components.

7.2 Variety theory basics for semigroups

A variety of semigroups is a class closed under taking homomorphic images, subsemigroups, and direct products. This framework organizes transformation semigroups by the identities they satisfy.

In practice, variety theory provides a way to identify broad families of semigroups that share algebraic laws, which can be used to infer structural constraints on transition behavior in automata or on decomposition patterns in transformation models.

7.3 Local structure around idempotents

Many decomposition approaches focus on the “local” picture near idempotents. Because idempotents stabilize images, one can analyze the semigroup by looking at the action restricted to images of idempotents and how maximal subgroups sit inside their \(\mathcal{H}\)-classes.

This local-to-global strategy is effective: global structure becomes understandable by combining information about stabilized layers and the symmetries occurring within them.

7.4 Rees matrix ideas for building blocks (semigroup viewpoint)

Rees matrix constructions describe certain semigroups using data from index sets, group components, and sandwich matrices. While transformation semigroups are not always directly representable in this exact form, Rees-theoretic ideas offer a general semigroup viewpoint: complex structures can be assembled from simpler group-based blocks arranged according to ideal class relations.

In structural studies, such conceptual tools guide how one might break down a transformation semigroup into layers indexed by Green relations and governed by local group behavior at idempotents.

8. Complexity and Computability Aspects

8.1 Problems: membership, generation, and equality

Algorithmic questions in transformation semigroups commonly include:

  • Membership: given \(S=\langle G\rangle\) and a transformation \(f\), decide whether \(f\in S\).
  • Generation: compute or describe \(\langle G\rangle\) from generators.
  • Equality: given two generating sets or presentations, decide whether they generate the same subsemigroup.

These tasks are challenging because the semigroup may grow exponentially with the size of \(X\), quickly making brute-force closure infeasible.

8.2 Computing products and normal forms (practical angle)

When generators are explicit transformations, computing products corresponds to composing functions. However, forming long products without collapsing is costly, and semigroups may contain many distinct elements.

Normal form ideas aim to represent elements efficiently, often using intermediate invariants such as rank and kernel partition to reduce redundant computations. Even when complete canonical forms are hard, partial normalizations can guide search procedures.

8.3 Size bounds and growth rates of generated semigroups

The growth of \(\langle G\rangle\) depends strongly on the structure of the generators. Some generator sets lead to rapid saturation of \(\mathcal{T}(X)\), while others produce small semigroups with restricted images and many idempotent-induced collapses.

Upper bounds often follow from counting transformations by rank and from stratifications induced by kernels or Green relations. Lower bounds can be obtained by constructing large sets of distinct iterates or by identifying many elements in different ideal classes.

8.4 Algorithmic uses of ranks and kernels

Ranks and kernels provide efficient invariants. Since composition can only decrease rank under typical conditions, one can use rank tracking to prune search trees. Kernel partitions can similarly guide equivalence checks: if two elements have different kernel refinement relationships inconsistent with possible compositions, they cannot be reachable through certain generator sequences.

These invariants do not always fully determine membership, but they frequently accelerate computation and yield meaningful complexity estimates.

9.1 Transformation groups vs transformation semigroups

When all transformations are bijective, the structure becomes a transformation group (indeed, a permutation group). The semigroup case allows non-invertible behavior, introducing new phenomena such as collapsing of images and presence of many idempotents.

Comparing the two clarifies which properties rely on invertibility and which are genuinely semigroup-theoretic.

9.2 Partial transformations and inverse hull connections

Partial transformation models allow functions defined only on subsets of \(X\). In that setting, one can connect to inverse semigroups and to structures that behave more like “local bijections” between subsets.

These variants are useful when modeling systems with conditional operations or undefined transitions, where total functions on \(X\) are too restrictive.

9.3 Semigroups of endomorphisms of algebraic structures

Instead of acting on a bare set, one can let transformations respect additional structure. For an algebraic structure \(A\) (such as a group, ring, or module), an endomorphism is a map preserving the operations of \(A\). The set of endomorphisms is closed under composition, forming a transformation semigroup inside the endomorphism monoid.

This “structure-preserving” restriction changes the possible ranks and kernel behaviors and often makes the semigroup more tractable.

9.4 Bi-ordered / ordered variants (high-level overview)

Some semigroup variants carry extra order or compatibility data, leading to ordered semigroups or bi-ordered settings. These augmentations can enforce monotonicity constraints on how transformations compare, refine the classification of elements, and support stronger decomposition results.

At a high level, such variants generalize the transformation semigroup framework while incorporating additional algebraic or order-theoretic constraints.

10. Applications and Further Directions

10.1 Modeling state evolution in automata and networks

Transformation semigroups are a natural language for modeling iterative state updates where each input step applies a deterministic function. In automata theory, the transition semigroup captures all reachable state evolutions and supports algebraic analysis of language recognition and computational properties.

Outside classical automata, similar semigroup models apply to discrete-time networks where each step is a fixed update rule from a library.

10.2 Connections to combinatorics of partitions

Kernels of transformations correspond to partitions of \(X\). Studying how these partitions refine or merge under composition links semigroup behavior to combinatorial partition theory.

This correspondence is especially useful when analyzing rank changes and when interpreting Green relations through the lens of how images and preimages behave.

In coding and protocol analysis, one often studies systems where messages are transformed by deterministic update procedures. While the specific mathematics varies, transformation semigroup techniques provide a vocabulary for describing the closure of achievable states under repeated application of allowable operations.

The algebraic viewpoint can help characterize which behaviors are stable, which sequences lead to collapse, and how composition constraints affect overall performance.

10.4 Open research themes and survey pointers

Active directions include:

  • sharper bounds for generation and membership problems in finite transformation semigroups,
  • classification of structural types for particular families of generated subsemigroups,
  • algorithmic techniques exploiting ranks, kernels, and Green structures,
  • connections between synchronizing behavior, idempotent abundance, and decomposition theorems.

Surveys in semigroup theory and automata-related algebra often provide entry points into these themes, especially for readers interested in how algebraic invariants translate into computation and dynamics.