Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. In mathematical analysis, the term also appears in the theory of one-parameter operator semigroups: see C0-semigroup.

The binary operation of a semigroup is most often denoted multiplicatively: ${\displaystyle x\cdot y}$, or simply ${\displaystyle xy}$, denotes the result of applying the semigroup operation to the ordered pair ${\displaystyle (x,y)}$. Associativity is formally expressed as that ${\displaystyle (x\cdot y)\cdot z=x\cdot (y\cdot z)}$ for all ${\displaystyle x}$, ${\displaystyle y}$ and ${\displaystyle z}$ in the semigroup. An example of a semigroup is that formed by string concatenation, which glues together strings. For example, the concatenation of the strings "spot " and "run" is the string "spot " • "run" = "spot run". Associativity means that

"See " • ("spot " • "run") = "See " • "spot run" = "See spot run" = "See spot " • "run" = ("See " • "spot ") • "run".

The formal study of semigroups began in the early 20th century. Early results include a Cayley theorem for semigroups realizing any semigroup as a transformation semigroup, in which arbitrary functions replace the role of bijections in group theory. A deep result in the classification of finite semigroups is Krohn–Rhodes theory, analogous to the Jordan–Hölder decomposition for finite groups. Some other techniques for studying semigroups, like Green's relations, do not resemble anything in group theory.

The theory of finite semigroups has been of particular importance in theoretical computer science since the 1950s because of the natural link between finite semigroups and finite automata via the syntactic monoid. In probability theory, semigroups are associated with Markov processes. In other areas of applied mathematics, semigroups are fundamental models for linear time-invariant systems. In partial differential equations, a semigroup is associated to any equation whose spatial evolution is independent of time.