Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Presentation of a monoid
Résumé
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.
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 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. We denote by (respectively ) the equivalence relation (respectively, the congruence) 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 (for an inverse semigroup) and an inverse semigroup presented by .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.