Presentation of a monoid

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).
A "presentation" should not be confused with a "representation".
Construction.
The relations are given as a (finite) binary relation on . To form the quotient monoid, these relations are extended to monoid congruences as follows:
First, one takes the symmetric closure of . This is then extended to a symmetric relation by defining if and only if = and = for some strings with . Finally, one takes the reflexive and transitive closure of , which then is a monoid congruence.
In the typical situation, the relation is simply given as a set of equations, so that formula_1. 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 formula_4 for integers "i", "j", "k", as the relations show that "ba" commutes with both "a" and "b".
Inverse monoids and semigroups.
Presentations of inverse monoids and semigroups can be defined in a similar way using a pair
where
formula_6
is the free monoid with involution on formula_7, and
is a binary relation between words. We denote by formula_9 (respectively formula_10) the equivalence relation (respectively, the congruence) generated by "T".
We use this pair of objects to define an inverse monoid
Let formula_12 be the Wagner congruence on formula_7, we define the inverse monoid
"presented" by formula_5 as
In the previous discussion, if we replace everywhere formula_17 with formula_18 we obtain a presentation (for an inverse semigroup) formula_5 and an inverse semigroup formula_20 presented by formula_5.
A trivial but important example is the free inverse monoid (or free inverse semigroup) on formula_7, that is usually denoted by formula_23 (respectively formula_24) and is defined by
or