semigroup

semigroup A very simple algebraic structure comprising a set S on which there is defined an associative operation denoted by ◦ (compare group). The operator ◦ is assumed to take operands from the set and produce results that are also in S. When the set S is finite a semigroup can be described by giving the Cayley table of the operation ◦; otherwise it can be described by giving a rule for ◦.

Examples of semigroups include: strings with the operation of concatenation (joining together); the set of n×n matrices together with the operation of multiplication; the set of transformations of a set and the operation of composing functions; the integers and the operation of choosing the maximum (or minimum) of two elements. The set of integers together with subtraction does not constitute a semigroup.

Semigroups play a major role in the theory of sequential machines and formal languages. If M is a sequential machine then any input string induces a function over the state-set of M. The set of all such induced functions forms a semigroup of the machine under function composition (see Myhill equivalence, Nerode equivalence). Semigroups are also used in certain aspects of computer arithmetic. See also free semigroup, transformation semigroup, monoid.