*** Welcome to piglix ***

Presentation of a monoid


In algebra, a presentation of a monoid (or semigroup) is a description of a monoid (or semigroup) in terms of a set Σ of generators and a set of relations on the free monoid Σ (or free semigroup Σ+) 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 (also known as 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.

The relations are given as a (finite) binary relation R on Σ. To form the quotient monoid, these relations are extended to monoid congruences as follows.

First, one takes the symmetric closure RR−1 of R. This is then extended to a symmetric relation E ⊂ Σ × Σ by defining x ~Ey if and only if x = sut and y = svt for some strings u, v, s, t ∈ Σ with (u,v) ∈ RR−1. Finally, one takes the reflexive and transitive closure of E, which is then a monoid congruence.

In the typical situation, the relation R is simply given as a set of equations, so that . Thus, for example,


...
Wikipedia

...