Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Monoid
Summary
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids are semigroups with identity. Such algebraic structures occur in several branches of mathematics.
The functions from a set into itself form a monoid with respect to function composition. More generally, in , the morphisms of an 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.
A set S equipped with a binary operation S × S → S, which we will denote •, is a monoid if it satisfies the following two axioms:
Associativity For all a, b and c in S, the equation (a • b) • c = a • (b • c) holds.
Identity element There exists an element e in S such that for every element a in S, the equalities e • a = a and a • e = a hold.
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 (ab)c = a(bc) and ea = ae = a.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.