In algebra, a presentation of a monoid (or a presentation of a semigroup) is a description of a monoid (or a semigroup) in terms of a set Σ of generators and a set of relations on the free monoid Σ∗ (or the free semigroup Σ+) generated by Σ.
The monoid is then presented as the quotient of the free monoid (or the free semigroup) by these relations.
This is an analogue of a group presentation in group theory.
As a mathematical structure, a monoid presentation is identical to a string rewriting system (also known as a semi-Thue system).
Every monoid may be presented by a semi-Thue system (possibly over an infinite alphabet).
[1] A presentation should not be confused with a representation.
To form the quotient monoid, these relations are extended to monoid congruences as follows: First, one takes the symmetric closure R ∪ R−1 of R. This is then extended to a symmetric relation E ⊂ Σ∗ × Σ∗ by defining x ~E y if and only if x = sut and y = svt for some strings u, v, s, t ∈ Σ∗ with (u,v) ∈ R ∪ R−1.
Finally, one takes the reflexive and transitive closure of E, which then is a monoid congruence.
In the typical situation, the relation R is simply given as a set of equations, so that
Thus, for example, is the equational presentation for the bicyclic monoid, and is the plactic monoid of degree 2 (it has infinite order).
Elements of this plactic monoid may be written as
for integers i, j, k, as the relations show that ba commutes with both a and b.
Presentations of inverse monoids and semigroups can be defined in a similar way using a pair where
is the free monoid with involution on
, and is a binary relation between words.
) the equivalence relation (respectively, the congruence) generated by T. We use this pair of objects to define an inverse monoid Let
, we define the inverse monoid presented by
as In the previous discussion, if we replace everywhere
we obtain a presentation (for an inverse semigroup)
A trivial but important example is the free inverse monoid (or free inverse semigroup) on