Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are semigroups with identity. They occur in several branches of mathematics. For example, the functions from a set into itself form a monoid with respect to function composition. More generally, in category theory, the morphisms of an object to itself form a monoid, and, conversely, a monoid may be viewed as a category with a single object. In computer science and computer programming, the set of strings built from a given set of characters is a free monoid. Transition monoids and syntactic monoids are used in describing finite-state machines. Trace monoids and history monoids provide a foundation for process calculi and concurrent computing. In theoretical computer science, the study of monoids is fundamental for automata theory (Krohn–Rhodes theory), and formal language theory (star height problem). See Semigroup for the history of the subject, and some other general properties of monoids. Suppose that S is a set and • is some binary operation S × S → S, then S with • is a monoid if it satisfies the following two axioms: In other words, a monoid is a semigroup with an identity element. It can also be thought of as a magma with associativity and identity. The identity element of a monoid is unique. For this reason the identity is regarded as a constant, i. e. 0-ary (or nullary) operation. The monoid therefore is characterized by specification of the triple (S, • , e). Depending on the context, the symbol for the binary operation may be omitted, so that the operation is denoted by juxtaposition; for example, the monoid axioms may be written ( a b ) c = a ( b c ) {displaystyle (ab)c=a(bc)} and e a = a e = a {displaystyle ea=ae=a} . This notation does not imply that it is numbers being multiplied.