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.
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.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
semigroup