Presentation of a monoid


In algebra, a presentation of a monoid is a description of a monoid in terms of a set of generators and a set of relations on the free monoid generated by. The monoid is then presented as the quotient of the free monoid 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. Every monoid may be presented by a semi-Thue system.
A presentation should not be confused with a representation.

Construction

The relations are given as a 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. Thus, for example,
is the equational presentation for the bicyclic monoid, and
is the plactic monoid of degree 2. 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.

Inverse monoids and semigroups

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. We denote by the equivalence relation generated by T.
We use this pair of objects to define an inverse monoid
Let be the Wagner congruence on, we define the inverse monoid
presented by as
In the previous discussion, if we replace everywhere with we obtain a presentation and an inverse semigroup presented by.
A trivial but important example is the free inverse monoid on, that is usually denoted by and is defined by
or