## Quick Reference

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.

**From:**
semigroup
in
A Dictionary of Computing »

*Subjects:*
Computing.