1 Semigroups and basic definitions

1.1 Associativity and algebraic axioms

A semigroup is a pair \((S,\cdot)\) where \(S\) is a set and \(\cdot\) is a binary operation \(S\times S\to S\) that is associative, meaning \((ab)c=a(bc)\) for all \(a,b,c\in S\). The defining feature is that sequential composition is well-defined without assuming any notion of undoing or reversal.

Semigroups are often viewed as abstractions of processes: elements represent “steps,” and the product represents performing one step after another, with the convention that the bracketing of multiple steps does not affect the final outcome.

1.2 Morphisms, congruences, and subsemigroups

A semigroup homomorphism is a function \(\varphi:S\to T\) between semigroups such that \(\varphi(ab)=\varphi(a)\varphi(b)\). Homomorphisms preserve the operational structure, so they transport algebraic questions from one semigroup to another.

A congruence on a semigroup is an equivalence relation \(\sim\) compatible with multiplication: if \(a\sim b\) and \(c\sim d\), then \(ac\sim bd\). Quotienting by a congruence yields a new semigroup, providing a systematic way to “identify” elements while maintaining the associative law.

A subsemigroup is a subset closed under the operation. Most structural arguments in semigroup theory begin by isolating relevant subsemigroups and comparing them to the whole system via inclusions, congruences, or homomorphisms.

1.3 Monoids and groups as special cases

If a semigroup has an identity element \(e\) satisfying \(ea=a=ae\) for all \(a\), it is a monoid. Adding inverses leads to groups, where each element has a two-sided inverse. Semigroup theory generalizes these settings by retaining associativity while allowing the absence of identity and inverses.

Many semigroup constructions are best understood by comparison: properties that are automatic in groups (such as cancellation or the symmetry of actions) can fail dramatically in semigroups, making the study of idempotents and ideals particularly central.

1.4 Semigroups of transformations

A fundamental family of examples comes from transformations: let \(X\) be a set and consider all functions \(X\to X\) closed under composition. With composition as the operation, this set forms a semigroup, often called a transformation semigroup.

Transformation semigroups provide a concrete bridge between algebra and computation: composition corresponds to iterated application of state updates, and non-invertibility corresponds to irreversible information loss.

2 Core constructions and examples

2.1 Free semigroups and universal properties

The free semigroup on an alphabet \(A\) is the set of all nonempty words over \(A\), with concatenation as multiplication. It is characterized by a universal property: any function from \(A\) to a semigroup \(S\) extends uniquely to a homomorphism from the free semigroup to \(S\).

Free semigroups are the natural ambient objects for studying identities (equations that must hold universally) and for formulating equational reasoning in a purely syntactic way.

2.2 Ideals, Green’s relations, and principal factors

An ideal of a semigroup \(S\) is a subset \(I\) such that \(SI\subseteq I\) and \(IS\subseteq I\) (two-sided) or only one side inclusion holds (left or right ideals). Ideals organize semigroups into layered parts and support inductive arguments.

Green’s relations decompose semigroup elements by how they generate principal ideals:

  • \(\mathcal{L}\) relates elements with the same principal left ideals,
  • \(\mathcal{R}\) relates elements with the same principal right ideals,
  • \(\mathcal{J}\) relates elements with the same principal two-sided ideals,

and \(\mathcal{H}=\mathcal{L}\cap \mathcal{R}\).

These relations refine the internal structure and underpin major classifications via “principal factors,” which capture what happens between consecutive ideal layers.

2.3 Rees matrix and completely simple structures

A completely simple semigroup is a semigroup that is simple (has no nontrivial ideals) and whose idempotents satisfy a strong compatibility condition; in particular, it contains plentiful idempotents that control multiplication.

The Rees matrix theorem describes completely simple semigroups using matrix-like data: a sandwich structure built from index sets, a group component, and a so-called sandwich matrix. This yields explicit models and converts abstract questions into combinatorial and group-theoretic ones.

A closely related notion, completely 0-simple semigroups, accounts for a distinguished absorbing element \(0\). Rees-type representations extend to this setting with appropriate modifications.

2.4 Direct products and semidirect product analogs

The direct product of semigroups \(S\) and \(T\) has underlying set \(S\times T\) and multiplication \((s,t)(s',t')=(ss',tt')\). Direct products are useful for building examples and for analyzing behavior componentwise.

Semidirect product constructions have less direct form than in group theory, but analogs exist using actions by endomorphisms or transformation structures. These operations let one encode how one semigroup’s behavior can influence another’s evolution, a theme that reappears in automata and control applications.

3 Structure theory

3.1 Idempotents and regularity

An idempotent is an element \(e\) with \(e^2=e\). In semigroup theory idempotents play a role comparable to projections: they often encode stable “modes” of a process, where applying the corresponding step twice yields no further change.

A semigroup element \(a\) is regular if there exists \(b\) with \(aba=a\). A semigroup is regular if every element is regular. Regularity is a key structural property that enables factorization through idempotents and produces strong internal symmetries without requiring inverses.

3.2 Regular semigroups and inverse semigroups

An inverse semigroup is a semigroup in which every element has a unique inverse with respect to the semigroup operation: for each \(a\) there exists \(a^{-1}\) such that \(aa^{-1}a=a\) and \(a^{-1}aa^{-1}=a^{-1}\), and this inverse is unique. Inverse semigroups generalize groups while allowing partial invertibility encoded by idempotents.

Regular semigroups include inverse semigroups but are broader; they admit robust structural tools such as decompositions around idempotents and relations among Green classes.

3.3 Completely 0-simple and completely simple semigroups

Completely simple and completely 0-simple semigroups are central in structure classification programs because they serve as building blocks for more complex semigroups via decomposition into ideal layers. The presence of many idempotents allows one to control multiplication and to represent the semigroup by Rees-type data.

In practice, these classes often appear as “core” dynamical components: their simplicity corresponds to strong mixing properties without nontrivial invariant ideals, while the completely 0-simple case models absorbing failure or termination behavior.

3.4 Decompositions and factorization approaches

Decomposition methods take advantage of the ideal structure: a semigroup can often be analyzed by separating it into simpler constituents associated with Green’s relations and quotient structures.

Factorization approaches study how elements can be expressed in terms of simpler generators, sometimes using normal forms or conditions on how idempotents and regular elements interact. Such methods are both theoretical and computational, since they can reduce questions to checking identities, membership in ideals, or properties of components.

4 Representation theory and semigroup actions

4.1 Actions on sets and induced transformation semigroups

A semigroup action on a set \(X\) is a map \(S\times X\to X\) such that \(s(st\cdot x)=(st)\cdot x\) in the appropriate associativity form. When the action is specified, each \(s\in S\) defines a transformation of \(X\), and the resulting transformations form a transformation semigroup.

This viewpoint connects semigroup theory to automata and dynamical systems. Different actions of the same abstract semigroup can yield markedly different behavior, so the representation via transformations is both a classification tool and an application instrument.

4.2 Representation via semigroup algebras

Given a field (or commutative ring) \(k\), one forms the semigroup algebra \(kS\): formal finite linear combinations of elements of \(S\), with multiplication induced bilinearly from the semigroup operation. Modules over this algebra provide an algebraic representation of the semigroup’s action.

Semigroup algebras turn semigroup questions into questions about linear operators and module structure, enabling techniques from ring theory and homological algebra to enter the field.

4.3 Modules over semigroup algebras

A \(kS\)-module is an algebraic structure where elements of \(S\) act linearly, extending the semigroup action concept to vector spaces. Submodules and quotient modules mirror invariant substructures within the semigroup action.

Studying these modules can reveal decomposition properties, growth behavior of representations, and the extent to which the semigroup resembles “semisimple” objects or instead exhibits complicated extensions and nilpotent phenomena.

4.4 Characters and semisimple vs. non-semisimple behavior

In group representation theory, characters classify irreducible representations. For semigroups, the picture is more delicate: representations need not behave semisimply, and the presence of nilpotent or non-diagonalizable behavior can complicate character theory.

Still, one can define analogs of characters and study how semigroup representations decompose. A recurring theme is distinguishing regimes where the semigroup algebra is close to semisimple (leading to cleaner decomposition) from regimes where radicals and extensions dominate (leading to more intricate representation structure).

5 Identities, varieties, and equational reasoning

5.1 Semigroup identities and word equations

A semigroup identity has the form \(u=v\), where \(u\) and \(v\) are words in variables, and the meaning is that substituting elements of a semigroup for variables makes the equality hold. Identities capture the “laws” of a class of semigroups.

Word equations and identity checking are central because many structural properties—such as finiteness of certain quotients, periodicity features, or constraints on idempotents—can be translated into equational form.

5.2 Varieties of semigroups

A variety of semigroups is a class closed under taking homomorphic images, subsemigroups, and direct products. This is analogous to Birkhoff’s theorem in universal algebra, where equationally defined classes correspond to varieties.

Varieties provide a systematic organization of semigroups by their equational behavior rather than by explicit multiplication tables. Classification can then focus on what identities are satisfied rather than on raw structure.

5.3 Pseudovarieties and profinite methods

For finite semigroups, closure properties lead to pseudovarieties, which are typically defined using finite homomorphic images and certain product constructions. Profinite techniques replace finite words by limits of finite structures, yielding topological tools for studying identities “in the limit.”

These methods are especially useful in formal language theory, where the behavior of a language class can correspond to a profinite algebraic property.

5.4 Computational aspects of equational theories

Equational reasoning invites algorithmic questions: given identities or a presentation of a semigroup, can one decide whether a target identity holds? Can one compute invariants such as the syntactic monoid or determine membership in a variety?

Computational aspects often hinge on finiteness assumptions. For finite semigroups, algorithmic approaches can leverage multiplication tables, while for general or infinite settings, decidability can fail or become highly constrained.

6 Formal languages and automata connections

6.1 Syntactic semigroups of languages

For a language \(L\) over an alphabet \(A\), one defines a syntactic semigroup (or monoid) capturing how words act by distinguishability with respect to membership in \(L\). Two words are equivalent if they cannot be told apart by appending any context on either side.

This construction turns language-theoretic properties into algebraic properties of a finite semigroup, making it possible to classify language families by algebraic constraints.

6.2 Recognizability and algebraic language theory

A language is recognizable if some finite semigroup (typically via a morphism to a finite monoid) can decide membership by mapping words to elements and then applying an acceptance condition.

This gives an algebraic counterpart to automata theory: automaton transition structures correspond to semigroup actions, and acceptance corresponds to subsets closed under appropriate transformations.

6.3 Aperiodic semigroups and temporal/logical characterizations

In many settings, languages corresponding to aperiodic semigroups are those that do not require counting arbitrarily long periodic patterns. Algebraically, aperiodicity corresponds to the absence of nontrivial group-like behavior inside the syntactic semigroup.

These algebraic characterizations align with logical and temporal descriptions in formal language theory, linking semigroup structure to expressive capabilities of certain logic fragments.

6.4 Decision procedures and complexity considerations

Determining algebraic properties of syntactic semigroups can support decision procedures for membership in language classes. For example, given a regular language representation (such as a DFA), computing its syntactic semigroup and checking whether it satisfies an algebraic condition can decide whether the language lies in a target family.

Complexity depends heavily on the representation size, the algebraic property being checked, and whether one operates with word equations, identity bases, or profinite approximations.

7 Factorization, decomposition, and combinatorial methods

7.1 Factorization of elements and normal forms

Many semigroup problems reduce to understanding how an element can be factorized into products with constrained forms. Normal forms, when available, provide canonical ways to represent elements, facilitating proofs and computations.

Factorizations often use idempotents, regular elements, or Green-related data to control how parts of a product interact, turning an abstract multiplication question into a combinatorial one.

7.2 Combinatorial invariants and enumerations

Semigroup theory frequently studies combinatorial invariants such as sizes of Green classes, counts of idempotents, ranks of principal ideals, and parameters measuring how complex the multiplication structure is.

Enumeration questions may focus on counting semigroups in a given class or counting distinct behaviors realized by semigroup actions. Such results connect semigroup structure to broader combinatorics.

7.3 Cayley graphs of semigroup actions

Given a semigroup \(S\) acting on a set \(X\), one can build a Cayley graph-like object describing how elements of \(S\) move points in \(X\). In the transformation viewpoint, edges represent application of generators.

These graphs support reachability and decomposition analyses, and they enable comparisons to random walk models and mixing properties, which are helpful both in pure theory and in applied modeling.

7.4 Random walks and probabilistic semigroup models

Random processes driven by semigroup actions—choosing generators according to a probability distribution—lead naturally to probabilistic models. Products of random elements correspond to iterated random transformations.

Such models can reveal typical behavior, convergence phenomena, and the emergence of stationary distributions or absorbing patterns, all while reflecting the underlying algebraic structure of the acting semigroup.

8 Applications to discrete event systems and computation

8.1 State-transition models as semigroups

Discrete event systems can often be represented as state-transition models where events compose sequentially. When transitions are irreversible or when some sequences collapse multiple states, the set of transition functions forms a semigroup under composition.

This algebraic representation captures how the order of applied events yields consistent outcomes without requiring reversibility, matching the semigroup framework.

8.2 Compositional modeling of workflows

Workflow systems can be modeled as compositions of steps with constraints on how actions combine. Semigroup composition naturally corresponds to concatenating process fragments, making it suitable for describing modular workflows.

Algebraic properties such as ideal structure can reflect bottlenecks, irreversible stages, or failure modes, especially when some steps lead to terminal or absorbing behaviors.

8.3 Synchronization and concurrency via transformation structures

Synchronization and concurrency in discrete systems frequently involve combining updates in structured ways. Transformation semigroups provide a language for combining effectful steps, including scenarios where parallel behavior can be encoded through sequentialized transformations under a chosen convention.

The semigroup perspective helps track what information survives synchronization and how repeated application of certain control actions stabilizes or collapses system states.

8.4 Robustness under non-invertible dynamics

Many computational processes involve simplification, compression, or loss of information—features that translate to non-invertible operations. Semigroup theory is well suited to analyze robustness: how repeated updates behave when they are not reversible.

By studying idempotents, regularity, and convergence under random or deterministic iteration, one can characterize which parts of the system stabilize, which parts retain memory, and which sequences lead to collapse.

9.1 Markov chains driven by semigroup actions

A common applied setup is to define a Markov chain where each step corresponds to applying a randomly chosen semigroup element (or generator). The state space may be the set on which the semigroup acts, while the transition probabilities derive from the chosen distribution on generators.

This framework unifies algebraic composition with probabilistic evolution: the semigroup structure determines which transitions are possible and how they compose over time.

9.2 Convergence and limit behavior

Convergence in such Markov models often reflects the presence of absorbing sets, periodic components, or idempotent-driven collapse. Algebraic decomposition of the semigroup can correlate with limiting distributions or with rates at which probabilities concentrate.

Analyzing long products of semigroup elements—whether deterministic or random—becomes an avenue for predicting steady-state behavior in discrete systems.

9.3 Ergodic-type results for semigroup systems

Ergodic-type statements describe when time averages converge to ensemble averages and when the system “forgets” its starting state. In semigroup-driven dynamics, these results depend on whether the action is sufficiently mixing and whether the semigroup contains structures that enforce stabilization.

Algebraic features such as aperiodicity or regularity can influence whether the dynamics exhibit convergence, periodicity, or persistent memory.

9.4 Moment methods and spectral viewpoints

Spectral methods study operators associated with the semigroup action or the induced Markov transition operator. Moments of observables along trajectories can be studied using eigenvalue information and decomposition into invariant subspaces.

When semigroup algebras are used, the spectral properties of corresponding linear operators can connect representation theory to analytic behavior, providing a toolbox for both qualitative and quantitative predictions.

10 Research directions and open problems (survey level)

10.1 Classification programs by identity and structural constraints

A major research direction is classification: organizing semigroups (or language classes) by which identities they satisfy or which structural properties they exhibit, such as bounded complexity of Green’s relations or controlled behavior of idempotents.

Open problems often ask for sharper classification boundaries, improved descriptions of varieties and pseudovarieties, or new invariants that distinguish semigroups beyond coarse equivalence.

10.2 Algorithms for computing semigroup invariants

Another active area concerns computation: given an explicit semigroup (often finite) or an automaton presentation of a language, researchers seek efficient algorithms to compute invariants such as syntactic semigroups, Green-class structures, or bases for relevant identity theories.

Many challenges arise from the tradeoff between algebraic expressiveness and computational cost, especially when invariants require exploring large closure properties.

10.3 Bridges to automata, logic, and profinite algebra

Research continues to refine correspondences between semigroup structure and logical/automata expressiveness. Profinite methods provide a unifying bridge, translating between algebraic constraints and the behavior of recognizable languages under limits.

Open directions include extending these bridges to broader classes, improving proof techniques, and finding more direct algebraic criteria for language or logic properties.

10.4 Semigroup models in emerging computational paradigms

Semigroup models appear in modern computational settings that emphasize composition, transformation, and constrained control—examples include resource-sensitive computation, streaming transformations, and workflow orchestration.

Research questions include identifying which semigroup subclasses best capture the dynamics of these paradigms, how to integrate probabilistic or learning-based components, and how algebraic invariants can inform system verification and analysis.