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
Operation , operation
1. A function from Sm (see Cartesian product) into S itself, where S is some set specific to the function. Such a function is usually refer… Boolean Algebra , Boolean algebra is often referred to as the algebra of logic, because the English mathematician George Boole, who is largely responsible for its begi… operate , op·er·ate / ˈäpəˌrāt/ • v. 1. [tr.] (of a person) control the functioning of (a machine, process, or system): a shortage of workers to operate new ma… Operator , op·er·a·tor / ˈäpəˌrātər/ • n. 1. a person who operates equipment or a machine: a radio operator. ∎ (usu. the operator) a person who works for a tele… Set Theory , A set is a collection of things. A set can consist of real or literal numbers (such as 1, 2, 3, 4 or a, b, c, d) or of objects (such as baseballs or… Set (seth) , set1 / set/ • v. (set·ting ; past set ) 1. [tr.] put, lay, or stand (something) in a specified place or position: Dana set the mug of tea down | Cath…
You Might Also Like
NEARBY TERMS
semigroup