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 . Thus, for example,

is the equational presentation for the bicyclic monoid, and

is the plactic monoid 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, and

is a binary) the equivalence relation (respectively, the congruence) generated by T.

We use this pair of objects to define an inverse monoid

be the Wagner congruence, we define the inverse monoid

presented as

we obtain a presentation (for an inverse semigroup) presented.

A trivial but important example is the free inverse monoid (or free inverse semigroup) and is defined by

or

Notes

References

• John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford

• M. Kilp, U. Knauer, A.V. Mikhalev, Monoids, Acts and Categories with Applications to Wreath Products and Graphs, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, 2000, .

• Ronald V. Book and Friedrich Otto, String-rewriting Systems, Springer, 1993, , chapter 7, "Algebraic Properties"